题目链接：CodeForces-1082G Increasing Frequency
有$n$个点，$m$条边，每个点和每条边都有一个权值，要求你从所给的图中选出一个子图，使得$\sum{val_{edges}}-\sum{val_{vertices}}$的值最大，子图的边集需满足：每条边关联的两个结点都在子图的点集中。
比较裸的最大权闭合子图，将边和点都转化为流网络中的点，因为边权贡献为正，所以源点$s$向代表原图边的结点连边，权值为边权，因为点权贡献为负，所以代表原图点的结点向汇点$t$连边，权值为点权，由于需满足子图每条边关联的两个结点都要在子图点集中，所以代表边$(u,v,w)$的结点向代表$u,v$的结点各连一条边权为无穷大的边，表示其不能是割边，然后跑最大权闭合子图即可。
最大权闭合子图详解：传送门
#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; }
CodeForces-1082G Increasing Frequency
原文：https://www.cnblogs.com/kangkang-/p/11314186.html
