【模板】最小点权覆盖集 & 最大点权独立集
大意
求一张二分图的最小点权覆盖集 & 最大点权独立集
思路
首先，我们考虑这样的问题，对于这样的匹配来说的处理方式，为了使得左右匹配，我们一般选择在中间的二分图的边建容量为 \(\infty\) 的边，这样就不会被割掉了，为什么要求最小割呢？
对于一条边：
\[S \xrightarrow{\text{容量 } w_u} u \xrightarrow{\text{容量 } \infty} v \xrightarrow{\text{容量 } w_v} T
\]
我们将其左右两边的边割掉一个，那么就是相当于选择了一个点覆盖了中间这个边，最终我们只需要让 \(S\) 与 \(T\) 不连通，就是求最小割。
这样求出的一定是一个最大匹配，那么我们考虑直接建 \(S\) 向 \(I_L\) 连边，容量为 \(val_i\)，\(I_R\) 向 \(T\) 连边，容量为 \(val_i\)，中间就连容量为 \(\infty\) 的边，如下图：
这样跑出的最小割来说，绿色的是割边，那么我们选出的点就是 \(2, 4, 5\)，这样我们就求出了我们的最小点权覆盖集。
对于最大点权独立集，与最小点权覆盖集为互补关系。
代码
#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;cin >> n >> m;S = 0;T = 2 * n + 1;for(int i = 1;i <= n;i ++){cin >> w;addedge(S, i, w);}for(int i = n + 1;i <= 2 * n;i ++){cin >> w;addedge(i, T, w);}for(int i = 1;i <= m;i ++){cin >> u >> v;addedge(u, v, INF);}cout << Dinic() << endl;DFS(S);for(int i = 1;i <= 2 * n;i ++){if(i <= n && !vis[i]){cout << i << " ";}else if(i > n && vis[i]){cout << i << " ";}}return 0;
}