thostever @ 2021-04-07 19:41:57
找不同找了半天了
#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;
}
by Chydz @ 2021-04-07 20:01:28
@___風 有重边
by koishi_offical @ 2021-04-07 20:06:32
a[x][y]=z; 改为a[x][y]+=z (或者改成邻接表