BZOJ3712 [PA2014]Fiolki

BZOJ

分析

容易看出整个过程构成一棵二叉树,那么两种物质一定在 LCA 处发生反应。

考虑反应发生的顺序。显然 LCA 深度大的反应先发生;如果 LCA 的深度相同,那么优先级高的先发生。

因此建树后排个序模拟一下就好了。

建议写树剖 LCA,这题树剖 LCA 的时间是倍增 LCA 的 1/2。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10,Q=500000+10;

int n,m,k,g[N];

struct edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int rt[N],cnt;
inline int find(int x) { return x==rt[x]?x:rt[x]=find(rt[x]); }

int dep[N],dis[N],fa[N],sz[N],hson[N],top[N];
inline void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

struct query { int u,v,lca,id; } q[Q];
inline int cmp(query a,query b) {
    return dep[a.lca]!=dep[b.lca]?dep[a.lca]>dep[b.lca]:a.id<b.id;
}

int main() {
    n=cnt=read(),m=read(),k=read();
    for (re int i=1;i<=n;++i) g[i]=read();
    for (re int i=1;i<=n+m;++i) rt[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),p=find(u),q=find(v);
        rt[p]=rt[q]=++cnt,addEdge(cnt,p),addEdge(cnt,q); 
    }
    for (re int i=1;i<=n+m;++i)
        if (find(i)==i) dfs1(i,0),dfs2(i,i);
    for (re int i=1;i<=k;++i) {
        int u=read(),v=read();
        q[i]=(query){u,v,getlca(u,v),i};
    }
    sort(q+1,q+k+1,cmp); ll ans=0;
    for (re int i=1;i<=k;++i) {
        int u=q[i].u,v=q[i].v;
        if (find(u)^find(v)) continue;
        int w=min(g[u],g[v]);
        ans+=w<<1,g[u]-=w,g[v]-=w;
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 11 月 05 日 10 : 22 AM

发表评论