LOJ#6631. 「EC Final 2018」异国情调的……古城 / Exotic … Ancient City 题解

发布于 2021-07-22  248 次阅读


题意

题目链接

有 $n$​ 行 $m+1$​ 列格点,第 $1$​ 列和第 $2$​ 列格点之间有 $e$ 条边,第 $i$ 条边的边权为 $c_i$,保证联通。第 $i$ 与 $i+1$ 列中的边是由第 $1$ 列和第 $2$ 列的边复制得到的。对于前 $i$ 列($2 \le i \le m+1$),求对于前 $i$ 列的点与端点都在前 $i$​​ 列的边构成的图,这张图的最小生成树所有边的权值和为多少。

数据范围:$1≤n≤10^5,1≤m≤10^5,1≤e≤10^6,1≤c≤30$​​​。

解析

首先考虑第 $1$ 列和第 $2$ 列之间的边数肯定不少于后面第 $i$ 与第 $i+1$ 列,因为前两列之间的点一定是完全没有联通起来的,而后面各列由于前面已经有很多边了,可能会存在第 $i$ 列有一些边已经被联通起来了。

接着考虑对于第 $i$ 列和第 $i+1$​ 列,这两列之间所连的边一定包含在第 $i-1$ 和第 $i$ 列的边中,因为第 $i-1$ 列初始被联通的边,一定不会因为某些操作而在第 $i$ 列中不联通,若有这些操作一定是不优的。因此在情况可能不变也可能更优的情况下,接下来两列一定不会选择之前没有被使用过的边,这同样是不优的。

因此,在边数较多时,可以先对于前两列跑一次最小生成树,非树边可以直接扔掉。

接着我们只需要考虑接下来两列比前两列少掉哪些边就可以了。我们发现正常去做的话非常难以维护删去边的权值,即保留边的权值。又发现边权范围较小,可以考虑差分思想,每次处理权值 $\le i$​​​ 的边,这些边每成功多联通了两个联通块,就令 $dif++$​​​,这样相当于边权为 $1$​​​ 的边能创造 $29$​​​ 的差分贡献,边权为 $2$​​​ 的边能创造 $28$​​​ 的差分贡献(最后是需要减去差分贡献的),以此类推。

回到去哪些边的问题。同样是每次处理权值 $\le i$ 的边。以第一二列转移到第二三列为例,如果第一二列中的某些边使第 $2$ 列中的某些点联通了,例如使点 $u$ 和点 $v$ 联通,而如果原来的连边也能够使点 $u$ 和点 $v$ 联通,那么这些边就组成了环,即需要去掉一条边。显然 $i$ 越大出现这样的情况越好,因为我们希望删掉的边尽可能大,因此这次这些被断的边对于差分数组的贡献是负的,即使 $dif--$,如果我们删掉了一条边权为 $1$ 的边,他对差分数组就会产生 $-29$ 的贡献。

问题来了,明明是删边,怎么贡献还少了呢?其实是没有问题的,因为第一二列之间需要连 $2n-1$ 条边,而第二三列之间本来就只需要连 $n$ 条边,因此一定会有一些边被删去,只是删的边不同贡献不同而已。

那么后面几列怎么理解呢?可以认为由于某些点初始被连上了,导致从 $2n-1$​ 删到 $n$​ 条边的过程中你所删除的边是权值较小的,可以抽象的认为你用一条边权为 $30$ 的边取代了他,因此他会给差分数组继续产生负贡献。

最后,将差分数据求前缀和求出原数组,再将原数组求前缀和求出前缀和数组,再输出答案即可。

讲得比较抽象,但是以我的水平好像也只能抽象理解了qwq。

代码

代码参考:zyy。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
struct edge{
    int u,v,w;
}e[N],ee[N],E[N];
int fa[N],n,Q,m;
ll dif[N];
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline bool cmp(edge i,edge j){
    return i.w<j.w;
}
inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
inline int read(){
    int x=0;
    char ch=gc();
    for (;ch<48||ch>57;ch=gc());
    for (;ch>=48&&ch<=57;ch=gc())
        x=x*10+ch-48;
    return x;
}
signed main(){
    n=read();Q=read();m=read();
    for(int i=1;i<=m;i++)
        e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=2*n;i++) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v+n);
        if(u!=v){
            fa[u]=v;
            e[++cnt]=e[i];
        }
    }
    m=cnt;
    for(int i=2;i<=30;i++){
        cnt=0;
        for(int j=1;j<=2*n;j++) fa[j]=j;
        for(int j=1;j<=m;j++){
            if(e[j].w<i){
                int u=find(e[j].u),v=find(e[j].v+n);
                if(u!=v){
                    dif[1]++;
                    if(u>v) swap(u,v);
                    fa[u]=v;
                    if(u>n) E[++cnt]=(edge){u-n,v-n,0};
                }
            }
            else break;
        }
        for(int j=2;j<=Q;j++){
            if(!cnt) break;
            int tot=cnt;cnt=0;
            for(int k=1;k<=tot;k++){
                int u=find(E[k].u),v=find(E[k].v);
                if(u==v) dif[j]--;
                else{
                    if(u>v) swap(u,v);
                    fa[u]=v;
                    if(u>n) E[++cnt]=(edge){u-n,v-n,0};
                }
            }
        }
    }
    for(int i=2;i<=Q;i++) dif[i]+=dif[i-1];
    for(int i=2;i<=Q;i++) dif[i]+=dif[i-1];
    for(int i=1;i<=Q;i++){
        printf("%lld\n",30*((ll)n*(i+1)-1)-dif[i]);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣