题解 CF1082G 【Petya and Graph】

· · 题解

题意

定义图权 = 图中边权总和 - 图中点权总和（空图的图权 = 0），求 n 个点 m 条边的无向图最大权子图。

解题思路

本题同 P4174。（别问我为什么，我也不知道为什么 CF 弄出个 NOI 原题出来，建议爆破）

最大权闭合子图模板题。

闭合子图，满足子图中的点的入度等于原图中对应的点。说白了，要选一个东西，必须把其依赖的东西全部先选上。

常见应用是有一类物品，有代价选择，但把指定的一组物品全选了会产生收益。

考虑用配合网络流的最小割 = 最大流解决，把问题放在二分图上，连边如下：

源点（S）往 有代价物品（A）连其代价。

有代价物品（A）往选了它可能产生收益的组（B）连 \infty。

每个组（B）往 汇点（T）连其收益。

先把全部收益加在一起，最后减去最大流（最小割），即为答案。

感性理解，如果某个组在代价处就已经割断了，通过最小割，我们增加了代价，但保住了收益，如果割掉收益，说明这个组的收益不优，宁愿不要它，于是抵消了收益，但没有代价。

回来看这道题，其实本质一模一样。

每条边 = 一个组，收益 = 边权，而组需要的物品 = 点，代价 = 点权。能看出来，交给模板就行啦。

代码实现

要开 long\ long！（当时直接粘模板 WA 了两发）

#include <cstdio>
#include <cstring>
#include <algorithm>

inline int read() {
    char c = getchar(); int n = 0; bool f = false;
    while (c < '0' || c > '9') { if (c == '-') { f = true; } c = getchar(); }
    while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
    return f ? -n : n;
}

const int maxN = 5005, maxE = 100005;

int n, m, s, t, dis[maxN], q[maxN];
long long ans;
bool vis[maxN];

struct List {
    int len, fst[maxN], nxt[maxE], v[maxE], w[maxE], fl[maxE];

    List() { memset(fst, -1, sizeof(fst)); }
    inline void insert(int u, int vv, int ww) { v[len] = vv, w[len] = ww, nxt[len] = fst[u], fst[u] = len++; }
    inline void connect(int u, int vv, int ww) { insert(u, vv, ww), insert(vv, u, 0); }
} ls;

bool bfs() {
    memset(dis, 0, sizeof(dis)); dis[q[1] = s] = 1;
    for (int l = 1, r = 1; l <= r; l++) {
        int u = q[l];
        for (int i = ls.fst[u]; ~i; i = ls.nxt[i]) {
            int v = ls.v[i], w = ls.w[i], fl = ls.fl[i];
            if (!dis[v] && fl < w) {
                dis[v] = dis[u] + 1;
                if (v == t) { return true; }
                q[++r] = v;
            }
        }
    }
    return false;
}
long long dinic(int u, long long f) {
    if (u == t) { return f; }
    long long lef = f;
    vis[u] = true;
    for (int i = ls.fst[u]; ~i; i = ls.nxt[i]) {
        int v = ls.v[i], w = ls.w[i], fl = ls.fl[i];
        if (dis[v] == dis[u] + 1 && fl < w && !vis[v]) {
            long long df = dinic(v, std::min(lef, (long long) w - fl));
            if (!df) { dis[v] = 0; continue; }
            lef -= df; ls.fl[i] += df; ls.fl[i ^ 1] -= df;
            if (!lef) { break; }
        }
    }
    vis[u] = false;
    return f - lef;
}

int main() {
    n = read(); m = read(); s = 0; t = n + m + 1;
    for (int i = 1; i <= n; i++) { ls.connect(s, i, read()); } // 源点 到 第一层 连 代价.
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read(); ans += w;
        ls.connect(u, n + i, 1e9); ls.connect(v, n + i, 1e9); // 第一层 到 第二层 连 inf.
        ls.connect(n + i, t, w); // 第二层 到 汇点 连 收益.
    }
    while (bfs()) { ans -= dinic(s, 1e18); }
    printf("%I64d\n", ans);
    return 0;
}