自闭了,求助

P3376 【模板】网络最大流

JK_LOVER @ 2020-07-27 09:39:09

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int read()
{
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}

const int N = 1800100;
struct Dinic{
    int head[N],cur[N],dis[N],s,t,n,cnt;
    struct E{int cap,flow,to,nxt;}e[N];
    void add(int x,int y,int cap)
    {
        e[++cnt].nxt = head[x];
        e[cnt].flow = 0;
        e[cnt].cap = cap;
        e[cnt].to = y;
        head[x] = cnt;
    }
    int Dfs(int x,int a,int t)
    {
        if(x == t || a == 0) return a;
        int f = 0,flow = 0;
        for(int i = cur[x];~i;i = e[i].nxt)
        {
            int y = e[i].to;
            if(dis[x] + 1 == dis[y] && ((f = Dfs(y,min(a,e[i].cap - e[i].flow),t))>0))
            {
                a -= f;
                flow += f;
                e[i].flow += f;
                e[i^1].flow -= f;
                cur[x] = e[i].nxt;
                if(a == 0) break;
            }
        }
        if(flow == 0) dis[x] = 0;
        return flow;
    }
    bool Bfs(int s,int t)
    {
        queue<int> Q;
        memset(dis,0,sizeof(dis));
        Q.push(s);dis[s] = 1;
        while(Q.size())
        {
            int x = Q.front();Q.pop();
            for(int i = head[x];~i;i = e[i].nxt)
            {
                int y = e[i].to;
                if(e[i].cap > e[i].flow && !dis[y])
                {
                    dis[y] = dis[x] + 1;
                    Q.push(y);
                    if(dis[t])
                    {
                        return true;
                    }
                }
            }   
        }
        return false;
    }
}MaxFlow;
int n,m,s,t;
long long maxflow = 0;
signed main()
{
    n = MaxFlow.n = read();m = read();
    s = MaxFlow.s = read();t = MaxFlow.t = read(),MaxFlow.cnt = -1;
    memset(MaxFlow.head,-1,sizeof(MaxFlow.head));
    for(int i = 1;i <= m;i++)
    {
        int a = read(),b = read(),cap = read();
        MaxFlow.add(a,b,cap);
        MaxFlow.add(b,a,0);
    }
    while(MaxFlow.Bfs(s,t))
    {
        for(int i = 1;i <= MaxFlow.n;i++) MaxFlow.cur[i] = MaxFlow.head[i];
        maxflow += MaxFlow.Dfs(s,0x3f3f3f3f,t);
    }
    cout<<maxflow<<endl;
}

by a___ @ 2020-07-27 09:54:56

您dfs里 cur[x]=e[i].nxt 应该放在 if 外面改成 cur[x]=i


by 樱巫女Official @ 2020-07-27 09:57:23

cur[x] = e[i].nxt;if(a == 0) break;后面


by a___ @ 2020-07-27 09:58:32

@JK_LOVER


by a___ @ 2020-07-27 09:59:56

额,楼上说的应该也可以


by JK_LOVER @ 2020-07-27 10:04:34

@a___ @樱巫女Official 谢谢


by JK_LOVER @ 2020-07-27 10:06:03

@樱巫女Official 为什么放在后面是对的啊/kk


by a___ @ 2020-07-27 10:10:35

@JK_LOVER 因为最后一次次流出可能没流满


by JK_LOVER @ 2020-07-27 10:12:58

@a___ 那就是我可能还有残留网络,而我直接判掉了,哦,谢谢,太感谢了


|