题解：P5036 随机生成树

· · 题解

P5036 随机生成树

题意概括

其实就是满足要求的连通块数量最大值。

思路

可以很快地想到 Kruskal 算法，但这题的难点不在这。

难点在于其要求的排序方式：

  1. 对连通块有贡献的优先。
  2. 满足条件一时，编号之和最小的优先。
  3. 同时满足条件二时，连接的两个点编号的之中较小的一个较小的边优先。

这里的排序条件 cmp 应该是：

bool cmp(edge a,edge b){
    if (a.w==b.w){
        if (a.u+a.v==b.u+b.v){
            return min(a.u,a.v)<min(b.u,b.v);
        }
        return a.u+a.v<b.u+b.v;
    }
    return a.w>b.w;
}

还有一个需要考虑的是如何判断贡献：

如果一条边的两端点的颜色 c[i] 和 c[i] 是相同的，显而易见的，连通块的数量会少，也就是其对生成连通块没有贡献。

代码

最后是代码，其他的注释都在里面了：

#include <bits/stdc++.h>
using namespace std;

const int N=500005;

int n,c[N],f[N],cnt;        //声明变量 

struct edge{
    int u,v,w;      //边要开多一点 
}e[10000005];

int find(int x){
    if (x==f[x]) return x;
    else return f[x]=find(f[x]);        //经典并查集 
}

bool cmp(edge a,edge b){        //排序规则 
    if (a.w==b.w){
        if (a.u+a.v==b.u+b.v){
            return min(a.u,a.v)<min(b.u,b.v);
        }
        return a.u+a.v<b.u+b.v;
    }
    return a.w>b.w;
}

void kruskal(){
    for (int i=1;i<=cnt;i++){
        int fa1=find(e[i].u);
        int fa2=find(e[i].v);
        if (fa1==fa2) continue;
        f[fa1]=fa2;
        cout << e[i].u << " " << e[i].v << endl;        //Kruskal 
    }
}

int main(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> c[i];     //读入 
    for (int i=1;i<=n;i++) f[i]=i;      //初始化 
    for (int i=1;i<=n;i++){
        for (int j=i*2;j<=n;j+=i){      //这里可以满足题里必须要连自身约数倍数 
            e[++cnt].u=i;
            e[cnt].v=j;
            if (c[i]==c[j]) e[cnt].w=-114514;
            else e[cnt].w=1919810;
        }       //只要能分辨就行，数字不重要 
    }
    sort(e+1,e+1+cnt,cmp);      //排序
    kruskal();
    return 0;
}