2024杭电多校（5） 1008. 猫咪们狂欢【带权最大独立集】

题意

给定两颗大小为 $n$ 的树，现在 $n$ 只猫中有 $k$ 只猫是狂欢猫，每只猫 $i$ 只能在第一颗或第二课树的 $i$ 号节点。
每棵树的每一条边都有一个边权，当这条边的两个点都有狂欢猫，就累加到答案上
求最大答案

思路

对于每条边来说，如果要满足它（两端点 $u,v$ 都有狂欢猫），那么在另一颗树上就一定会有若干条与 $u,v$ 相连的边无法满足
所以对于每条边，它会与另一颗树上的某些边产生矛盾，我们在它们之间连边表示矛盾

那么我们将边抽象成点后，将它们的矛盾用边表示，每个点有一个点权就是这条边对应的边权
那么我们的目标就等价于在这张图上找出一个带权最大独立集

进一步观察发现：这张图是二分图，所以我们只需要跑 $Dinic$，用点权之和减去最小割即为答案

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;constexpr int inf = 1E9;template<class T>
struct Dinic {struct _Edge {int to;T cap;_Edge(int to, T cap) : to(to), cap(cap) {}};int n; //点的数量，编号从 1 开始std::vector<_Edge> e; //链式前向星std::vector<std::vector<int>> g; //起到链式前向星nxt的作用std::vector<int> cur; //当前弧优化std::vector<int> h; //深度Dinic() {}Dinic(int n) {init(n);}void init(int n) {this->n = n;e.clear();g.assign(n + 1, {});cur.resize(n + 1);h.resize(n + 1);}bool bfs(int s, int t) { //构造分层图h.assign(n + 1, -1);std::queue<int> que;h[s] = 0;que.push(s);while (!que.empty()) {const int u = que.front();que.pop();for (int i : g[u]) {auto [v, c] = e[i];if (c > 0 && h[v] == -1) { //下一层有容量的邻居h[v] = h[u] + 1;if (v == t) {return true;}que.push(v);}}}return false;}T dfs(int u, int t, T f) {if (u == t) {return f;}auto r = f;for (int &i = cur[u]; i < int(g[u].size()); ++i) {const int j = g[u][i];auto [v, c] = e[j];if (c > 0 && h[v] == h[u] + 1) {auto a = dfs(v, t, std::min(r, c));e[j].cap -= a;e[j ^ 1].cap += a;r -= a; //r是剩余可用流量if (r == 0) {return f;  //如果r用完，说明f跑满了}}}return f - r; //否则f-r就是已用流量}void addEdge(int u, int v, T c) {g[u].push_back(e.size()); //记录在e中的下标e.emplace_back(v, c);g[v].push_back(e.size()); //反向边e.emplace_back(u, 0);}T flow(int s, int t) {T ans = 0;while (bfs(s, t)) {cur.assign(n + 1, 0); //当前弧初始化ans += dfs(s, t, std::numeric_limits<T>::max());}return ans;}std::vector<bool> minCut() { //最小割std::vector<bool> c(n + 1);for (int i = 1; i <= n; i++) {c[i] = (h[i] != -1);}return c;}struct Edge {int from;int to;T cap;T flow;};std::vector<Edge> edges() {std::vector<Edge> a;for (int i = 0; i < e.size(); i += 2) {Edge x;x.from = e[i + 1].to;x.to = e[i].to;x.cap = e[i].cap + e[i + 1].cap;x.flow = e[i + 1].cap;a.push_back(x);}return a;}
};const int N = 1005;struct Edge{int u;int v;int w;
};std::vector<std::pair<int, int>> f[N];
Edge e1[N], e2[N];int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){int n, k;std::cin >> n >> k;std::vector<bool> cat(n + 1, false);fore(i, 0, k){int x;std::cin >> x;cat[x] = true;}int ans = 0;fore(i, 1, n){int u, v, w;std::cin >> u >> v >> w;e1[i] = {u, v, w};if(cat[u] && cat[v]) ans += w;}fore(i, 1, n){int u, v, w;std::cin >> u >> v >> w;e2[i] = {u, v, w};if(cat[u] && cat[v]) ans += w;f[u].push_back({v, i});f[v].push_back({u, i});}Dinic<int> dinic(2 * n + 5);int S = 2 * n + 1, T = S + 1;fore(i, 1, n){auto [u, v, w] = e1[i];if(cat[u] && cat[v]) dinic.addEdge(S, i, w);}fore(i, 1, n){auto [u, v, w] = e2[i];if(cat[u] && cat[v]) dinic.addEdge(i + n, T, w);}fore(i, 1, n){auto [u, v, w] = e1[i];for(auto [x, j] : f[u]) dinic.addEdge(i, j + n, inf);for(auto [x, j] : f[v]) dinic.addEdge(i, j + n, inf);}std::cout << ans - dinic.flow(S, T) << endl;fore(i, 1, n + 1) f[i].clear();}return 0;
}