U103816 【模板】最大权闭合子图
大意
求最大权闭合子图。
思路
首先，对于这个题目来说，我们首先要明确一个问题，对于一个点 \(i\)，其所有出边所指向的点所构成的集合为 \(I_{out}\)，那么说，我们只要选择了 \(i\) 点，就必须选择 \(I_{out}\) 中的所有点。
这个题的值在点上，我们想要选择是尽可能多的正权值的点，尽可能少的负权值的点，这个事情我们可以交给最小割来处理。我们做这样的建模，建立 \(S\) 源点，表示你不选择正权点 \(a\) 所构成的集合，建立 \(T\) 汇点，表示你选择负权点 \(b\) 所构成的集合。由 \(S\) 向每一个正权的点连容量为 \(val\) 的边，由每个负权点向 \(T\) 连容量为 \(-val\) 的边。
这时候就有人要问了：主播主播，那你如何保证子图是闭合的？
好问题，我们只需要保证如果选了 \(i\) 点，那么 \(I_{out}\) 不会被割到另一边，这种约束我们直接连一条容量为 \(\infty\) 的边，这样就永远不会被最小割割掉。
这个时候我们求出的最小割代表的含义就是：选择某些负点付出的代价 + 不选某些正点付出的代价。
显然我们最后的答案是 \(\sum val_i(val_i > 0) - \text{mincut}\)
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 1000;
const int MAX_M = 100000;
struct edge {int v, c, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {memset(p, -1, sizeof(p));eid = 0;
}
void insert(int u, int v, int c) {e[eid].v = v;e[eid].next = p[u];e[eid].c = c;p[u] = eid++;
}
void addedge(int u, int v, int c) {insert(u, v, c);insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {memset(d, -1, sizeof(d));queue<int> q;q.push(S);d[S] = 0;while (!q.empty()) {int u = q.front();q.pop();for (int i = p[u]; i != -1; i = e[i].next) {int v = e[i].v;if (e[i].c > 0 && d[v] == -1) {q.push(v);d[v] = d[u] + 1;}}}return (d[T] != -1);
}
int dfs(int u, int flow) {if (u == T) {return flow;}int res = 0;for (int i = p[u]; i != -1; i = e[i].next) {int v = e[i].v;if (e[i].c > 0 && d[u] + 1 == d[v]) {int tmp = dfs(v, min(flow, e[i].c));flow -= tmp;e[i].c -= tmp;res += tmp;e[i ^ 1].c += tmp;if (flow == 0) {break;}}}if (res == 0) {d[u] = -1;}return res;
}
int Dinic() {int res = 0;while (bfs()) {res += dfs(S, INF);}return res;
}bool vis[MAX_N];
void DFS(int u){vis[u] = true;for(int i = p[u];i != -1;i = e[i].next){if(!vis[e[i].v] && e[i].c){DFS(e[i].v);}}
}int main() {init();int n, m, w, u, v, sum = 0;cin >> n >> m;S = 0;T = n + 1;for(int i = 1;i <= n;i ++){cin >> w;if(w > 0){addedge(S, i, w);sum += w;}else if(w < 0){addedge(i, T, -w);}}for(int i = 1;i <= m;i ++){cin >> u >> v;addedge(u, v, INF);}cout << sum - Dinic() << endl;// DFS(S);// for(int i = 1;i <= n;i ++){// if(vis[i]){// cout << i << " ";// }// }// cout << endl;return 0;
}