题目传送门(BZOJ)

题解 :

对于每次操作的两瓶药, 如同建立Kruskal重构树那样建立一棵重构树
这样建立好树之后, 每次操作的反应都一定会在两个物质的LCA处发生
所以, 我们按LCA深度为第一关键字, 按优先级为第二关键字排序, 就符合了发生反应的顺序
然后对于每次拿出的两瓶药, 取一个最小的乘2更新答案, 然后它们两个的质量分别减掉这个最小值即可
思路比较清晰, 码量略大, 100行/2K左右

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define rev(i, p) for(EDGE* i = h[p]; i; i = i->next) #define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++char buf[100000], *p1, *p2;inline char gc() { char ch = nc(); while(isspace(ch)) ch = nc(); return ch;}inline int rd() { int x = 0, f = 1; char ch = nc(); while(!isdigit(ch)) ch = nc(); while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc(); return x*f;}const int N = 400400; struct EDGE { int to; EDGE *next;}*h[N], e[N<<1];struct DATA { int dep, cur, x, y; inline bool operator < (const DATA &A) const { return dep == A.dep ? cur < A.cur : dep > A.dep; }}a[N<<1];inline void addEdge(int u, int v) { static int _; EDGE * t = &e[++_]; t->to = v, t->next = h[u], h[u] = t;}long long ans;int g[N>>1], f[N];int n, m, K, cnt, tot;int fa[N], top[N], siz[N], son[N], dep[N];int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}void dfs(int p) { siz[p] = 1; dep[p] = dep[fa[p]]+1; rev(i, p) { fa[i->to] = p; dfs(i->to); if(siz[i->to] > siz[son[p]]) son[p] = i->to; siz[p] += siz[i->to]; }}void dfs(int p, int t) { top[p] = t; if(son[p]) dfs(son[p], t); rev(i, p) if(i->to != son[p]) dfs(i->to, i->to);}int lca(int x, int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y;}int main() { cnt = n = rd(), m = rd(), K = rd(); for(int i = 1; i <= n; i ++ ) g[i] = rd(); for(int i = 1; i<=n*2; i ++ ) f[i] = i; for(int i = 1; i <= m; i ++ ) { int u = find(rd()), v = find(rd()); f[u] = f[v] = ++cnt; addEdge(cnt, u), addEdge(cnt, v); } for(int i = 1; i <= n; i ++ ) if(!dep[i]) { int u = find(i); dfs(u); dfs(u, u); } for(int i = 1; i <= K; i ++ ) { int u = rd(), v = rd(); if(find(u) == find(v)) { ++ tot; a[tot].dep = dep[lca(u, v)]; a[tot].cur = i; a[tot].x = u; a[tot].y = v; } } sort(a+1, a+tot+1); for(int i = 1; i <= tot; i ++ ) { int x = a[i].x, y = a[i].y; int det = min(g[x], g[y]); ans += det*2; g[x] -= det, g[y] -= det; } printf("%lld\n", ans);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<