wa#5求助

P3376 【模板】网络最大流

RainFestival @ 2019-06-02 11:10:16

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue> 
int n,m,s,t,dep[10005],ans;
std::vector<int> a[10005],b[10005],f[10005];
std::queue<int> q;
void add(int x,int y,int v)
{
    a[x].push_back(y);
    a[y].push_back(x);
    b[x].push_back(v);
    b[y].push_back(0);
    f[x].push_back(a[y].size()-1);
    f[y].push_back(a[x].size()-1);
}
int bfs(int s,int e)
{
    for (int i=1;i<=n;i++) dep[i]=0;
    q.push(s);dep[s]=1;
    while (!q.empty())
    {
        int v=q.front();q.pop();
        for (int i=0;i<a[v].size();i++)
            if (b[v][i]>0&&!dep[a[v][i]])
            {
                dep[a[v][i]]=dep[v]+1;
                q.push(a[v][i]);
            }
    }
    if (dep[e]) return 1;
    return 0;
}
int dfs(int v,int now,int e)
{
    if (v==e||!now) return now;
    int flow=0;
    for (int i=0;i<a[v].size();i++)
        if (b[v][i]&&dep[v]+1==dep[a[v][i]])
        {
            int k=dfs(a[v][i],std::min(now,b[v][i]),e);
            b[v][i]=b[v][i]-k;
            b[a[v][i]][f[v][i]]=b[a[v][i]][f[v][i]]+1;
            now=now-k;
            flow=flow+k;
        }
    return flow;
}
int dinic(int s,int t)
{
    int sumflow=0;
    while (bfs(s,t)) sumflow=sumflow+dfs(s,2000000000,t);
    return sumflow;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i=1;i<=m;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        add(x,y,v);
    }
    int ans=dinic(s,t);
    printf("%d\n",ans);
    return 0;
} 

|