题解 CF1515F【Phoenix and Earthquake】

· · 题解

CF1515F Phoenix and Earthquake

更好的阅读体验

下分场/ll

这道题其实很简单，考场降智想复杂写了个类似Brovuka的算法，然后被自己hack了/kk。

题意

给定一个n个点m条边的无向联通图，在一次地震中边都被摧毁了。

位置i有a_i吨沥青，修建一条边需要X吨沥青，因此连边的两个连通块的沥青吨数之和要大于等于X，你需要修建n-1条边使得图联通，求是否能做到，如果能，请输出任意一种方案。

1\leqslant n,m\leqslant 3\times 10^5

分析

考虑猜一个结论：只要沥青总吨数total大于等于(n-1)X，那么一定可以使图联通。

证明：考虑不断找到一条连接两个沥青总吨数大于等于X的边进行修建。 若已经修建了e条边后无法找到下一条边，那么可知total-eX<X+(n-e-2)X（左边是当前沥青总吨数，右边是考虑任意一条边两端的沥青总吨数加上其他连通块的沥青总吨数）。 因此taotal<(n-1)X，推出矛盾。

不难发现取该图的任意一个\text{dfs}树仍然满足条件，因此我们将图上的问题转换到了树上，而且易知树上每条边都要用到。

我们在树上进行\text{dfs}，x遍历完儿子y后，讨论连接(x,y)的边什么时候加入答案序列：如果x所在的连通块与y所在的连通块沥青总吨数大于等于X，那么可以直接连，否则可以放在最后连，用一个类似双端队列的东西就可以维护了。

由于每次可以直接把连接后儿子的沥青总吨数加到父亲上（没有连接的儿子不会影响父亲向上的连边），因此并不需要用并查集维护连通块的沥青总数。

时间复杂度：O(n+m)。

代码

#include<stdio.h>
const int maxn=300005,maxm=maxn<<1;
int n,m,X,e,cnt1,cnt2;
int start[maxn],to[maxm],then[maxm],id[maxm],ans[maxn],a[maxn],vis[maxn];
long long sum;
inline void add(int x,int y,int i){
    then[++e]=start[x],start[x]=e,to[e]=y,id[e]=i;
}
void dfs(int x){
    vis[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y])
            continue;
        dfs(y);
        if(a[x]+a[y]>=X)
            a[x]+=a[y]-X,ans[++cnt1]=id[i];
        else ans[--cnt2]=id[i];
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&X);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),sum+=a[i];
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,i),add(y,x,i);
    }
    if(sum<1ll*(n-1)*X){
        puts("NO");
        return 0;
    }
    puts("YES");
    cnt1=0,cnt2=n;
    dfs(1);
    for(int i=1;i<=n-1;i++)
        printf("%d\n",ans[i]);
    return 0;
}