P3639 [APIO2013] 道路费用
太 tm 宝藏了。
看到 \(k\) 的数据范围，很难不让人想到 \(2^k\) 枚举边集。
因为当枚举的边集确定后，其最大价值是很好算的，只需用每一条非树边去约束即可。
但直接做肯定是不行的，因为 \(k\) 去到了 \(20\)。
不难发现每次都跑一遍最小生成树重复计算的边很多，考虑将原图简化。
发现存在一些旧边每次都会被加入，可以将这些边处理出来。处理的过程也很简单，将所有新边加入，再跑一遍最小生成树，此时被加入的旧边就是一定会被加入的边。
将这些边加入到图中并缩点，便剩下了最多 \(k+1\) 点，此时就可以再去 \(2^k\) 枚举子集做。
代码巨 tm 恶心
Code:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 7, M = 3e5 + 7, K = 27;
int n, m, k;
ll a[N], res[N];
int tt, nn;
int belong[N];
int vis[N];
ll minn[K];
struct edge_union{int from, to;ll w;
}ee[M], ne[K], pe[K];
struct uds{int fa[N];void init(int len){for(int i = 1; i <= len; i++) fa[i] = i;}int get(int x){if(fa[x] == x) return x;return fa[x] = get(fa[x]);}void merge(int x, int y){x = get(x), y = get(y);fa[x] = y;}
}A, B;
struct Edge{struct edge{int to;int pre;}e[K << 1];int head[K], tot;int fa[K], dep[K];ll sz[K];void init(){memset(head, 0, sizeof(head));memset(sz, 0, sizeof(sz));memset(dep, 0, sizeof(dep));memset(fa, 0, sizeof(fa));tot = 0;}void add(int x, int y){e[++tot] = {y, head[x]};head[x] = tot;}void dfs(int u, int father){fa[u] = father;sz[u] = res[u];dep[u] = dep[father] + 1;for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(v == father) continue;dfs(v, u);sz[u] += sz[v];}}void update(int u, int v, ll w){if(dep[u] < dep[v]) swap(u, v);while(dep[u] > dep[v]){minn[u] = min(minn[u], w);u = fa[u];}while(u != v){minn[u] = min(minn[u], w);minn[v] = min(minn[v], w);u = fa[u];v = fa[v];}}
}E;
bool cmp1(edge_union a, edge_union b){return a.w < b.w;
}
void build(){A.init(N - 7);B.init(N - 7);sort(ee + 1, ee + m + 1, cmp1);for(int i = 1; i <= k; i++){int u = ne[i].from, v = ne[i].to;A.merge(u, v);}for(int i = 1; i <= m; i++){int u = ee[i].from, v = ee[i].to;if(A.get(u) == A.get(v)) continue;A.merge(u, v);B.merge(u, v);}for(int i = 1; i <= n; i++){if(!vis[B.get(i)]){belong[i] = vis[B.get(i)] = ++nn;}else belong[i] = vis[B.get(i)];res[belong[i]] += a[i];}for(int i = 1; i <= k; i++){ne[i] = {belong[ne[i].from], belong[ne[i].to], 0};}for(int i = 1; i <= m; i++){int u = ee[i].from, v = ee[i].to;ll w = ee[i].w;if(B.get(u) == B.get(v)) continue;pe[++tt] = {belong[u], belong[v], w};B.merge(u, v);}sort(pe + 1, pe + tt + 1, cmp1);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m >> k;for(int i = 1; i <= m; i++){cin >> ee[i].from >> ee[i].to >> ee[i].w;}for(int i = 1; i <= k; i++){cin >> ne[i].from >> ne[i].to;}for(int i = 1; i <= n; i++){cin >> a[i];}build();ll ans = 0;for(int S = 0; S < (1 << k); S++){A.init(K);E.init();memset(minn, 0x3f, sizeof(minn));bool flg = 0;for(int i = 1; i <= k; i++){if((~S) & (1 << (i - 1))) continue;int u = ne[i].from, v = ne[i].to;if(A.get(u) == A.get(v)){flg = 1;break;}A.merge(u, v);E.add(u, v);E.add(v, u);}if(flg) continue;for(int i = 1; i <= tt; i++){int u = pe[i].from, v = pe[i].to;if(A.get(u) == A.get(v)) continue;A.merge(u, v);E.add(u, v);E.add(v, u);}E.dfs(belong[1], 0);for(int i = 1; i <= tt; i++){int u = pe[i].from, v = pe[i].to;ll w = pe[i].w;E.update(u, v, w);}ll sum = 0;for(int i = 1; i <= k; i++){if((~S) & (1 << (i - 1))) continue;int u = ne[i].from, v = ne[i].to;if(E.dep[u] < E.dep[v]) swap(u, v);sum += E.sz[u] * minn[u];}ans = max(ans, sum);}printf("%lld\n", ans);return 0;
}