刚学最大流,求改Dinic代码(8,9,10,WA了)
查看原帖
刚学最大流,求改Dinic代码(8,9,10,WA了)
444135
thostever楼主2021/4/7 19:41

找不同找了半天了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t;
int a[210][210];
int dis[210];
queue<int> q;
bool bfs()
{
	memset(dis,0,sizeof(dis));
	q.push(s);
	dis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int j=1;j<=n;j++)
		{
			if(a[u][j]<=0) continue;
			if(dis[j]) continue;
			dis[j]=dis[u]+1;
			q.push(j);
		}
	}
	return dis[t];
}
int dfs(int u,int in)
{
	if(u==t) return in;
	int out=0;
	for(int j=1;j<=n;j++)
	{
		if(a[u][j]<=0) continue;
		if(dis[j]!=dis[u]+1) continue;
		int res=dfs(j,min(in,a[u][j]));
		a[u][j]-=res;
		a[j][u]+=res;
		in-=res;
		out+=res;
	}
	if(out==0) dis[u]=0;
	return out;
}
signed main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z;
	}
	int ans=0;
	while(bfs())
	{
		ans+=dfs(s,1e18);
	}
	cout<<ans;
}
2021/4/7 19:41
加载中...