自己写：灌满一条增广路

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

一张管道网，0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多能过多少水。

找路那半已经写好了，b 是这条路上最细的一段。补上灌水这两步。外层的 for (round < 50) 是步数上限，防止没写完时死转，别删它。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 这张网每秒最多过多少水把卡住它的那一刀找出来 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// 管道网：0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多过多少水（0 表示没有这根管子）
using Cap = vector<vector<int>>;
Cap make_cap() {
    Cap c(7, vector<int>(7, 0));
    c[0][1] = 6; c[0][2] = 5; c[1][3] = 4; c[1][4] = 2; c[2][4] = 5;
    c[3][6] = 3; c[4][3] = 2; c[4][5] = 4; c[5][6] = 5;
    return c;
}
const Cap CAP = make_cap();

// Edmonds-Karp：反复用 BFS 找一条每段都还有余量的路，把它最细的那一段灌满；res 带回残量图
int maxflow(Cap cap, int s, int t, Cap* res = nullptr) {
    int n = cap.size(), flow = 0;
    for (int round = 0; round < 50; round++) {
        vector<int> par(n, -1);
        par[s] = s;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v = 0; v < n; v++) {
                if (cap[u][v] > 0 && par[v] == -1) {
                    par[v] = u;
                    q.push(v);
                }
            }
        }
        if (par[t] == -1) break;
        int b = INT_MAX;
        for (int v = t; v != s; v = par[v]) b = min(b, cap[par[v]][v]);
        // TODO: 沿路把正向容量各减 b，同时把反向容量各加 b；flow 加上 b
    }
    if (res) *res = cap;
    return flow;
}

int main() {
    cout << maxflow(CAP, 0, 6) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

自己写：灌满一条增广路

更多题目

全部评论