夏晓光(loveJY)的博客

From 2020省选复习

这个....是一个很大很大的东西,在没有完成一轮复习前我们还是不要考虑花式建图的复习了...

先把算法肝透吧

核心:最大流dinic

其实,这个没有什么好讲的(因为讲就太长了),注意我们反向边以及ccnt=1?

还有bfs的时候要flow[i]>0.....

还有当前弧优化,以及memcpy是前面为接受复制后面是复制体....

queue<int> que;
inline int bfs()
{
	while(!que.empty())que.pop();
	memset(h,0,sizeof(h));
	que.push(s);
	h[s]=1;
	while(!que.empty()) {
		int u=que.front();
		que.pop();
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			if(!h[v]&&flow[i]>0) {
				h[v]=h[u]+1;
				que.push(v);
			}

		}
		if(h[t])return 1;
	}
	return h[t];
}

inline int dfs(int u,int nflow)
{
	if(nflow==0||u==t)return nflow;
	int ret=nflow,a=0;
	for(int &i=cur[u]; i; i=nxt[i]) {
		int v=to[i];
		if(h[v]==h[u]+1&&(a=dfs(v,std::min(nflow,flow[i])))) {
			flow[i]-=a;
			flow[i^1]+=a;
			ret-=a;
			if(!ret)break;
		}
	}
	if(ret==nflow)h[u]=-1;
	return (nflow-ret);
}

算法2:最小费用最大流

如果没有负权??边,我们可以直接拍dijkstra费用流

而如果有的话我们要先跑spfa求出最短路加势再去dijkstra,每个边边权变成$h[u]-h[v]+w[i]$并且每跑完一次update一次势能函数...

然后这都很菜菜菜菜,zkw费用流吊打他们

具体就是先spfa把每个点的dis(最短路)值求出来,然后跑一个和dinic的dfs很像的东西,但是加上了如果下个点最短路是这个点延伸而来才扩展的限制,并且每个点只允许访问一次(vis数组)

也不难看出其实就是spfa费用流一次扩展多条路径.....

但是吊锤dijkstra

inline int spfa() {
	while(!que.empty())que.pop();
	for(int i=1; i<=t; ++i)
		dis[i]=-1e18;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	vis[s]=1;
	que.push(s);
	//spfa势能预处理
    //这个是zkw没有势能....
	while(!que.empty()) {
		int u=que.front();
		que.pop();
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			if(dis[v] < dis[u] + w[i] && flow[i] > 0) {
				dis[v]=dis[u]+w[i];
				if(!vis[v]) {
					vis[v]=1;
					que.push(v);
				}
			}
		}
		vis[u]=0;
	}
	return dis[t]>=-1e17;
}
int mrk[MAXN];
inline int dfs(int u,int nflow) {
	if(u==t) {
		maxcost+=dis[u]*nflow;
		return nflow;
	}
	mrk[u]=1;
	int ret=0;
	for(int &i=cur[u]; i; i=nxt[i]) {
		int v=to[i];
		if(!mrk[v]&&abs(dis[v]-dis[u]-w[i])<=eps&&flow[i]) {
			int a=dfs(v,min(nflow-ret,flow[i]));
			if(a) {
				flow[i]-=a;
				flow[i^1]+=a;
				ret+=a;
				if(ret==nflow)break;
			}
		}
	}
	return (ret);
}

inline void zkwcost() {
	maxcost=0;
	while(spfa()) {
		memcpy(cur,home,sizeof(home));
		memset(mrk,0,sizeof(mrk));
		dfs(s,1e9);
	}
}

最后一定要注意建边不能宏定义!!!!!!

一定要写两个函数.....TAT