求助,WA on #9~#10

P3376 【模板】网络最大流

wfawfas @ 2023-10-21 18:37:57

下面是源代码,求助

  • 怎么调#9#10都过不了

    
    #include<iostream>
    #include<climits>       //‘INT_MAX’ is defined in header ‘<climits>’
    #include<cstring>       //‘memset’ is defined in header ‘<cstring>’
    #include<queue>
    using namespace std;
    #define Max 100000
    #define LL long long
    struct edge
    {
    int next;       //同起点的边,连成一条链子
    int to;         //边指向的点
    LL w;           //边的权值
    }e[Max];
    int head[Max] = { 0 };
    int cnt = 0;
    void add_edge(int u, int v, LL w)
    {
    cnt++;
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];      //初始时,链子最后的元素.next=0
    head[u] = cnt;
    
    //建立反向边,使其编号为原边加1
    cnt++;
    e[cnt].to = u;
    e[cnt].w = 0;
    e[cnt].next = head[v];
    head[v] = cnt;
    }
    int n; int m;
    int s, t;
    int lv[Max];                    
    int cur[Max];                   
    int bfs()                       //bfs进行分层
    {
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    for (int i = 1; i <= n; i++)
        cur[i] = head[i];
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = e[eg].next)     
        {
            int to = e[eg].to;
            LL val = e[eg].w;
            if (val > 0 && lv[to] == -1)    
            {
                lv[to] = lv[p] + 1;
                q.push(to);
            }
        }
    }
    return lv[t] != -1;             //判断是否能到达终点
    }
    LL dfs(int p, LL flow)
    {
    if (p == t)
        return flow;
    LL rest = flow;
    for (int eg = cur[p]; eg&&rest; eg = e[eg].next)        //对该点起始的所有边进行遍历
    {
        cur[p] = eg;                        //把多次DFS弄到一起
        int to = e[eg].to;
        LL val = e[eg].w;
        if (val>0&&lv[to]==lv[p]+1)         //往深处DFS
        {                       
            LL c = dfs(to, min(val,rest));
            rest -= c;              //该点所能流过的流量减少,接着在寻找该点的其他边
            e[eg].w -= c;
            e[eg + 1].w += c;       //保证反向边紧接着正向边建立
            //构造残量网络
        }
    }
    return flow - rest;
    }
    LL Dinic()

{ LL Max_Flow = 0; while (bfs()) { Max_Flow += dfs(s, LONG_MAX); } return Max_Flow; } int main() { cin >> n >> m; cin >> s >> t; for (int i = 0; i < m; i++) { int u, v; LL w; cin >> u >> v >> w; bool temp = true; for (int eg = head[u]; eg; eg = e[eg].next) //对该点起始的所有边进行遍历 if (e[eg].to == v) { e[eg].w += w; temp = false; break; } if (temp) add_edge(u, v, w); } cout << Dinic(); return 0; }


by wfawfas @ 2023-10-21 18:39:01

已经处理过重边了


|