把卡住它的那一刀找出来

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

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

最大流跑完之后，残量图里从水源还走得到的点已经算进 side 了。把跨出 side 的那些原图管子收成割，输出最大流/割容量/割上有几条边。

（本题用 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;
}

int main() {
    Cap res;
    int f = maxflow(CAP, 0, 6, &res);
    // 残量图里从水源还走得到的那些点，就是割的「水源这一侧」
    vector<bool> side(7, false);
    side[0] = true;
    vector<int> st = {0};
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        for (int v = 0; v < 7; v++) {
            if (res[u][v] > 0 && !side[v]) {
                side[v] = true;
                st.push_back(v);
            }
        }
    }
    vector<int> cut;
    for (int u = 0; u < 7; u++) {
        for (int v = 0; v < 7; v++) {
            // TODO: 原图里有这根管子（CAP[u][v] > 0），u 在 side 里而 v 不在，它就在割上：把容量收进 cut
        }
    }
    int total = 0;
    for (int c : cut) total += c;
    cout << f << "/" << total << "/" << cut.size() << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

把卡住它的那一刀找出来

更多题目

全部评论