LOJ6001. 「网络流 24 题」太空飞行计划

发布于 18 天前  14 次阅读


Link

Sol

此题涉及一个经典的模型:最大权闭合子图。现在来分析一下。

什么叫做闭合子图?就是说,在一个子图中的任意一点,它的所有边连接的点都在这个子图中。那么最大权就是说,图中的点带点权,然后选出的这个闭合子图点权和要最大。

在这个题中,闭合子图的要求体现在一个实验E_j它必须要用到一个实验器材集合R_j \in II是所有的实验器材的集合。我们把实验与超级源点连一条容量为1的边。再连向这个实验要用的实验器材R_j,因为选了这个实验就必须选择这些器材,这些变不可以断开,容量设为inf。再把实验器材连一条容量为1的边向超级汇点。那么现在,我们就是要选出一个最大权闭合子图。

关于最大权闭合子图,有两个Claim

Claim1:最小割一定是简单割

简单割:割中的边都直接与源点或汇点相连

因为实验连向器材的边容量为inf,那么最小割一定不会割这些边。那么最小割只有可能割那些连向源汇点的边。所以最小割是简单割

Claim2:最大权闭合子图是简单割。

留作读者自行思考。

所以最后按照这样的方式把原图转化为最大权闭合子图的模型,跑最小割即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4e3 + 5;
const int inf = 0x7f7f7f7f, s = 3022, t = 3038;

int n, m, num = 1;
int head[SIZE], cur[SIZE], dep[SIZE];

struct node {
    int to, v, nxt;
} edge[SIZE << 1];

int read() {
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

void addEdge(int u, int v, int d) {
    edge[++ num] = (node) {v, d, head[u]}, head[u] = num;
}

int bfs() {
    std::queue < int > q;
    memset(dep, -1, sizeof(dep));
    dep[s] = 0, cur[s] = head[s], q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (dep[v] != -1 || edge[i].v <= 0) continue;
            dep[v] = dep[u] + 1, cur[v] = head[v], q.push(v);
            if (v == t) return 1;
        }   
    }
    return 0;
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int ans = 0, k = 0;
    for (int i = cur[u], v; i && flow; i = edge[i].nxt) {
        v = edge[i].to, cur[u] = i;
        if (edge[i].v > 0 && dep[v] == dep[u] + 1) {
            k = dinic(v, std::min(flow, edge[i].v));
            if (!k) continue;
            edge[i].v -= k, edge[i ^ 1].v += k, ans += k, flow -= k;
        }
    }
    if (!flow) dep[u] = -1;
    return ans;
}

int main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    scanf("%d %d", &m, &n);
    int maxFlow = 0, minCut = 0, tot = 0;
    for (int i = 1; i <= m; ++ i) {
        int val; scanf("%d", &val);
        addEdge(s, i, val); addEdge(i, s, 0);
        tot += val;
        while (getchar() == ' ') {
            scanf("%d", &val);
            addEdge(i, m + val, inf); addEdge(m + val, i, 0);
        }
    }   
    for (int i = 1, val; i <= n; ++ i) {
        scanf("%d", &val);
        addEdge(m + i, t, val); addEdge(t, m + i, 0);
    }
    while (bfs()) maxFlow += dinic(s, inf);
    minCut = tot - maxFlow;
    for (int i = 1; i <= m; ++ i) {
        if (dep[i] != -1 && i < m) printf("%d ", i);
        else if (dep[i] != -1 && i == m) printf("%d", i);
    }
    printf("\r\n");
    for (int i = 1; i <= n; ++ i) {
        if (dep[i + m] != -1 && i < n) printf("%d ", i);
        else if (dep[i + m] != -1 && i == n) printf("%d", i);
    }
    printf("\r\n%d\r\n", minCut);
    return 0;
}

学会生存 学会关心