73分蒟蒻求助!

P3376 【模板】网络最大流

寻逍遥2006 @ 2021-08-07 17:10:06

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,i,a,b;
long long ans;
int w[210][210],de[201],q[201],top,rea;
bool bfs()
{
    memset(de,0,sizeof(de));
    top=rea=1;
    q[1]=s;
    de[s]=1;
    while(top<=rea)
    {
        for(i=1;i<=n;i++)
        {
            if(de[i]==0&&w[q[top]][i]!=0)
            {
                de[i]=de[q[top]]+1;
                q[rea+1]=i;
                rea++;
            }
        }
        top++;
    }
    return de[t];
}
int dfs(int a,int minn)
{
    if(a==t)
    {
        ans+=minn;
        return minn;
    }
    else
    {
        int j,ret=0,g;
        for(j=1;j<=n;j++)
        {
            if(ret==minn) break;
            if(w[a][j]!=0&&de[j]==de[a]+1)
            {
                g=dfs(j,min(minn-ret,w[a][j]));
                w[a][j]-=g;
                w[j][a]+=g;
                ret+=g;
            }
        }
        return ret;
    }
}
int main()
{
    freopen("P3376_8.in","r",stdin);
    cin>>n>>m>>s>>t;
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        cin>>w[a][b];
    }
    while(bfs())
        dfs(s,0x7fffffff); 
    cout<<ans;
    return 0;
 } 

by Jr_Zlw @ 2021-08-07 17:56:45

大概是输入的边权可能为0?


by spdarkle @ 2021-08-07 18:07:06

是WA还是TLE?


by spdarkle @ 2021-08-07 18:09:40

容量好像没有0的,不然我的ISAP也没法过


by mofianger @ 2021-08-12 15:29:27

这道题有重边,您的cin>>w[a][b]应该改成 w[a][b] += ...@寻逍遥2006


|