刚学最大流,求改Dinic代码(8,9,10,WA了)

P3376 【模板】网络最大流

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 (或者改成邻接表


|