假的Dinic
查看原帖
假的Dinic
119261
7KByte楼主2020/6/17 16:53

Rt,估计以前写的都是错的,但是为啥从没有出现过问题。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 205
#define M 5005
typedef long long ll; 
using namespace std;
int h[N],tot=1;
struct edge{
	int to,nxt,cap;
}e[M<<1];
void add(int x,int y,int z){
	e[++tot].nxt=h[x];h[x]=tot;e[tot].cap=z;e[tot].to=y;
}
int n,m,s,t,d[N],cur[N];
queue<int>q;
bool bfs(){
	memset(d,0,sizeof(d));
	d[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		cur[x]=h[x];
		for(int i=h[x];i;i=e[i].nxt)
			if(e[i].cap&&!d[e[i].to])
				d[e[i].to]=d[x]+1,q.push(e[i].to);
	}
	return d[t];
}
int dfs(int x,int flow){
	if(x==t)return flow;
	int res=flow;
	for(int &i=cur[x];i;i=e[i].nxt){
		if(!res)return flow;
		if(e[i].cap&&d[x]+1==d[e[i].to]){
			int now=dfs(e[i].to,min(res,e[i].cap));
			if(!now)d[e[i].to]=1;
			else{
				e[i].cap-=now;
				e[i^1].cap+=now;
				res-=now;
			}
		}
	}
	return flow-res;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	rep(i,1,m){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,0);
	}
	ll ans=0;
	while(bfs())ans+=dfs(s,0x7fffffff);
	printf("%lld\n",ans);
	return 0;
}
2020/6/17 16:53
加载中...