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;
}