加粗哪根管子才真有用

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

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

给你一次加粗的机会。分别试试加粗最细的那根（1 → 4，从 2 到 4）和加粗割上的那根（3 → 6，从 3 到 5），连同原始值一起输出三个数。

（本题用 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]);
        for (int v = t; v != s; v = par[v]) {
            cap[par[v]][v] -= b;
            cap[v][par[v]] += b;
        }
        flow += b;
    }
    if (res) *res = cap;
    return flow;
}

Cap bump(int u, int v, int nc) {
    Cap c = CAP;
    c[u][v] = nc;
    return c;
}

int main() {
    int a = maxflow(CAP, 0, 6);
    // TODO: b：把 1 → 4 加粗到 4 再算一次；c：把 3 → 6 加粗到 5 再算一次
    int b = -1, c = -1;
    cout << a << "/" << b << "/" << c << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

加粗哪根管子才真有用

更多题目

全部评论