BZOJ 3712: [PA2014]Fiolki – [重构树]


题目传送门(BZOJ)

题解 :

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

代码 :

#include 
#include 
#include 
#include 
#include 
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原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注