CodeForces-1082G Increasing Frequency

迈不过友情╰ 2021-11-04 12:02 146阅读 0赞

题目链接：[CodeForces-1082G Increasing Frequency][]

## 题意 ##

有$n$个点，$m$条边，每个点和每条边都有一个权值，要求你从所给的图中选出一个子图，使得$\\sum\{val\_\{edges\}\}-\\sum\{val\_\{vertices\}\}$的值最大，子图的边集需满足：每条边关联的两个结点都在子图的点集中。

--------------------

## 思路 ##

比较裸的最大权闭合子图，将边和点都转化为流网络中的点，因为边权贡献为正，所以源点$s$向代表原图边的结点连边，权值为边权，因为点权贡献为负，所以代表原图点的结点向汇点$t$连边，权值为点权，由于需满足子图每条边关联的两个结点都要在子图点集中，所以代表边$(u,v,w)$的结点向代表$u,v$的结点各连一条边权为无穷大的边，表示其不能是割边，然后跑最大权闭合子图即可。

最大权闭合子图详解：[传送门][Link 1]

--------------------

## 代码实现 ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using std::queue;
    typedef long long LL;
    const int INF = 0x3f3f3f3f, N = 5010, M = 50010;
    int head[N], d[N];
    int n, m, s, t, tot;
    LL maxflow;
    struct Edge
    {
        int to, cap, nex;
    } edge[M];
    queue<int> q;
    void add(int x, int y, int z) {
        edge[++tot].to = y, edge[tot].cap = z, edge[tot].nex = head[x], head[x] = tot;
        edge[++tot].to = x, edge[tot].cap = 0, edge[tot].nex = head[y], head[y] = tot;
    }
    bool bfs() { // 在残存网络上构造分层图
        memset(d, 0, sizeof(d));
        while (q.size()) q.pop();
        q.push(s); d[s] = 1;
        while (q.size()) {
            int x = q.front(); q.pop();
            for (int i = head[x]; i; i = edge[i].nex) {
                int v = edge[i].to;
                if (edge[i].cap && !d[v]) {
                    q.push(v);
                    d[v] = d[x] + 1;
                    if (v == t) return true;
                }
            }
        }
        return false;
    }
    int dinic(int x, int flow) {  // 在当前分层图上增广
        if (x == t) return flow;
        int rest = flow, k;
        for (int i = head[x]; i && rest; i = edge[i].nex) {
            int v = edge[i].to;
            if (edge[i].cap && d[v] == d[x] + 1) {
                k = dinic(v, std::min(rest, edge[i].cap));
                if (!k) d[v] = 0;  // 剪枝，去掉增广完毕的点(当前弧优化)
                edge[i].cap -= k;
                edge[i^1].cap += k;
                rest -= k;
            }
        }
        return flow - rest;
    }
    
    int main() {
        while (~scanf("%d %d", &n, &m)) {
            s = 0, t = n + m + 1;
            tot = 1, maxflow = 0;
            memset(head, 0, sizeof(head));
            for (int i = 1, val; i <= n; i++) {
                scanf("%d", &val);
                add(i, n + m + 1, val);
            }
            LL sum = 0;
            for (int i = 1, u, v, val; i <= m; i++) {
                scanf("%d %d %d", &u, &v, &val);
                sum += val;
                add(0, n + i, val);
                add(n + i, u, INF);
                add(n + i, v, INF);
            }
            while (bfs()) maxflow += dinic(s, INF);
            printf("%I64d\n", sum - maxflow);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/kangkang-/p/11314186.html

[CodeForces-1082G Increasing Frequency]: http://codeforces.com/problemset/problem/1082/G
[Link 1]: https://www.cnblogs.com/kangkang-/p/11312773.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211104/5f438733b4ed4434a40ed1432729bbd7.png