EK算法 68pts #8 9 10 11WA求调

P3376 【模板】网络最大流

xialingn @ 2024-08-18 00:53:28

代码带有注释,求调

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5005;
const int flow_max = 0x7fffffff;
long long capa[maxn][maxn], flow[maxn];  //记录残留网络的容量,标记从源点到当前节点实际还剩多少流量可用
int n, m, s, t, pre[maxn];//点、边、源点、汇点;记录前驱并用来判断是否在队列的数组;
queue<int> q;

int bfs(int src, int des) {
    while(!q.empty()) q.pop();  //队列清空
    for (int i=1; i <= n; i++) pre[i] = -1; //此时未记录前驱且都不在队列中
    flow[src] = flow_max;
    pre[src] = 0;  
    q.push(src);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (v == des) break;  
        for (int i=1; i <= n; i ++) {  //未记录出边,直接遍历所有点
            if(capa[v][i] > 0 && i != src && pre[i] == -1) { //存在路径且该点既不是源点之前也未探索过
                q.push(i);
                pre[i] = v;
                flow[i] = min(capa[v][i], flow[v]); 
            }
        }
    }
    if (pre[des] == -1) return -1;  //残留图中不再存在增广路
    else return flow[des];  //一条增广路径上的流入汇点的流量
}

int maxFlow(int src, int des ) { 
    long long increase = 0; //每个增广路径的流量
    long long sumflow = 0;//总流量
    while ((increase = bfs(src, des)) != -1) {  //当图中还存在增广路径时
        int k = des;
        while(k != src) {
            int last = pre[k];
            capa[last][k] -= increase;
            capa[k][last] += increase;  //建立反向边
            k = last;
        }
        sumflow += increase;
    }
    return sumflow;
}

int main(void) {
    cin >> n >> m >> s >> t;
    memset(capa, 0, sizeof(capa));
    memset(flow, 0, sizeof(flow));
    //memset(pre, -1, sizeof(pre));  //不能在主函数里面更新,因为这样就只更新了一次
    int x, y;
    int c;
    for (int i=0; i < m; i ++) {
        cin >> x >> y >> c;
        capa[x][y] += c;  //重边就累加c
    }
    cout << maxFlow(s, t);
    return 0;
}

by cpchenpi @ 2024-09-03 21:07:46

你的 bfsmaxFlow 的返回值仍然是 int,改为 long long 立即通过。


|