Edmonds-Karp 90pts求助 #11WA

P3376 【模板】网络最大流

oval_m @ 2022-04-07 00:50:58

照着紫书打的,#11WA 手算了一下,找到了问题 但是不知道怎么改

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#define INF ((1uLL<<63)-1)
#define N 210
#define ll long long
using namespace std;
struct Edge
{
    int from,to;
    ll cap,flow;       //边的 容量 和 流量
    Edge(int fr,int t,ll ca,ll fl):from(fr),to(t),cap(ca),flow(fl){}
};
vector<Edge> edges;     //边的数组
vector<int> g[N];       //图 g[i][j] 为 edges的下标 即 edges[g[i][j]]
ll a[N];       //a[i]表示  s到i的路径上的最小残量   起点到i的可改进量  同时a还可以作为bfs的vis数组
int p[N];       //最短路树上p的入边编号
int n,m,s,t;        //节点数 边数  起点 终点   建图之后的总边数为原来的2倍(反向边)
void AddEdge(int u,int v,ll cap)
{
    int m = edges.size();
    edges.push_back(Edge(u,v,cap,0));
    edges.push_back(Edge(v,u,0,0));         //反向边
    //将正边和反边放一起 当正边为[j] 反边可以表示成 [j^1]  边的起点从0开始
    g[u].push_back(m);
    g[u].push_back(m+1);
}
ll EdmondsKarp()
{
    ll flow = 0;
    while(true)     //貌似每次循环就是一次增广?    //每次找一条最短路
    {
        memset(a,0,sizeof(a));
        queue<int> q;       //bfs
        q.push(s);      //起点
        a[s] = INF;     //起点的可改进量为无穷
        while(!q.empty())
        {
            int temp = q.front();q.pop();
            for(int i = 0; i < g[temp].size(); i++)
            {
                Edge& e = edges[g[temp][i]];
                if(!a[e.to] && e.cap>e.flow)        //该点没被访问过 && 这条边的流量还没有满
                {
                    a[e.to] = min(a[temp],e.cap-e.flow);     //可流向该点的流量为 起点有的和边剩余的流量 取最小值
                    p[e.to] = g[temp][i];       //记录 e.to这个节点在最短路中是由那条边走过来的
                    q.push(e.to);
                }
            }
            if(a[t])break;      //已经遍历到了终点 无需继续bfs
        }
        if(!a[t])break;         //出口
        //一下对edges数组的flow进行更改 为下次循环做准备
        for(int i = t; i != s; i = edges[p[i]].from)     //用p数组按照最短路回溯
        {
            edges[p[i]].flow += a[t];
            edges[p[i]^1].flow -= a[t];
        }
        flow += a[t];
    }
    return flow;
}
signed main()
{
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++)
    {
        int a,b;
        ll cap;
        cin >> a >> b >> cap;
        AddEdge(a,b,cap);
    }
    cout << EdmondsKarp();
    return 0;
}

|