蒟蒻三问最大流

Zvelig1205 @ 2022-08-05 10:36:05

by AIskeleton @ 2022-08-05 10:46:46

@极冬寒雪

#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
int re()
{
    int s=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        s=s*10+ch-48,ch=getchar();
    return s*f;
}
void wr(int s)
{
    if(s<0)putchar('-'),s=-s;
    if(s>9)wr(s/10);
    putchar(s%10+48);
}
const int N=207,M=5007;
int n,m,s,t,ans;
int fir[N],nex[M<<1],poi[M<<1],val[M<<1],cnt=1;
int arc[N];
void ins(int x,int y,int z)
{
    nex[++cnt]=fir[x];
    poi[cnt]=y;
    val[cnt]=z;
    fir[x]=cnt;
}
int dep[N];
bool bfs()
{
    queue<int>h;
    for(int i=1;i<=n;i++)
        dep[i]=2147483647,arc[i]=fir[i];
    dep[s]=0;h.push(s);
    while(h.size())
    {
        int now=h.front();h.pop();
        for(int i=fir[now];i;i=nex[i])
        {
            int p=poi[i];
            if(val[i]==0)continue;
            if(dep[p]==2147483647)
            {
                dep[p]=dep[now]+1;
                h.push(p);
            }
        }
    }
    return dep[t]!=2147483647;
}
int dfs(int now,int minn)
{
    if(now==t)
        return minn;
    int sum=0,ff;
    for(int i=arc[now];i;i=nex[i])
    {
        arc[now]=i;int p=poi[i];
        if(val[i]==0||dep[p]!=dep[now]+1)continue;
        ff=dfs(p,min(minn,val[i]));
        val[i]-=ff,val[i^1]+=ff;
        sum+=ff;minn-=ff;
        if(!minn) break;
    }if(!sum) dep[now]=2147483647;
    return sum;
}
signed main()
{
    n=re();m=re();s=re();t=re();
    for(int i=1;i<=m;i++)
    {
        int x=re(),y=re(),z=re();
        ins(x,y,z),ins(y,x,0);
    }
    while(bfs())
        ans+=dfs(s,2147483647);
    wr(ans);
    return 0;
}

稍微改了下，应该是dfs的问题，其实不加当前弧优化也是能过的。 不加当前弧优化 加当前弧优化

by Zvelig1205 @ 2022-08-05 11:03:34

@A_I_Skeleton 谢谢dalao，A 了/qq