70分RE求助

P3376 【模板】网络最大流

loris @ 2020-01-28 10:32:51

#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
struct edge
{
    int to;
    int nxt;
    int c;
}e[550000];
int p[200001],k=1;
bool used[200001];
void add(int u,int v,int w)
{
    e[k].nxt=p[u];
    p[u]=k;
    e[k].to=v;
    e[k].c=w;
    k++;
}
int dfs(int s,int t,int f)
{
    if(s==t)
        return f;
    used[s]=1;
    for(int i=p[s];i!=0;i=e[i].nxt)
    {
        if(!used[e[i].to]&&e[i].c>0)
        {
            int d=dfs(e[i].to,t,min(f,e[i].c));
            if(d>0)
            {
                e[i].c-=d;
                add(e[i].to,s,d);
                return d;
            }
        }
    }
    return 0;
}
int get_maxf(int s,int t)
{
    int maxf=0;
    int f;
    while(1)
    {
        memset(used,0,sizeof(used));
        f=dfs(s,t,INF);
        if(f==0)
            return maxf;
        maxf+=f;
    }
}
int main()
{
    int n,m,s,t,u,v,w;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<get_maxf(s,t);
    return 0;
}

by 宁_缺 @ 2020-02-02 23:20:09

@loris

\color{purple}\text{数组开小啦}

很高兴遇到一个和我一样路径数复制为1的,但这样你就要多开一个,不然就爆了

其他貌似都对的


by loris @ 2020-02-03 09:30:18

Thanks♪(・ω・)ノ


|