P5036 题解

Shaoxing_Sun · 2024-01-17 20:10:43 · 题解

题意

其实就是连通块最多有多少个嘛，这样我们就可以用 kruskal。

题解

主要是在 kruskal 中的排序怎么排，我们按照题意来写 cmp 函数，这可能也是本题较难的地方。

我们要保留更多的连通块，就把边权从大到小排序，其他的按照题意即可。

bool cmp(Edge a, Edge b) {
    if(a.w == b.w) { // 边权相等
        if(a.u + a.v == b.u + b.v) { // 起点和终点同样也相等
            return a.u < b.u; 
        }
        return a.u + a.v < b.u + b.v; // 比较和
    }
    return a.w > b.w; // 保留更多的连通块 
}

其他的就基本不难了，用调和级数初始化，连边就行了。

Code

#include <bits/stdc++.h> 
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr) 
#define rep(i, a, b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for (int i = a; i >= b; i--)
#define lc(x) x << 1ll 
#define rc(x) x << 1ll | 1ll
#define lowbit(x) ((x) & (-x))
#define LEN_LC (tree[lc(i)].r - tree[lc(i)].l + 1) 
#define LEN_RC (tree[rc(i)].r - tree[rc(i)].l + 1) 
#define LEN (tree[i].r - tree[i].l + 1)  

const int N = 5e5 + 7; 
const int M = 1e7 + 7;
struct Edge{    
    int u, v, w; 
}edge[M];
int dsu[N], c[N]; 

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

void init() {
    rep(i, 1, N) dsu[i] = i; 
}
int find(int x) {
    if(x != dsu[x]) {
        dsu[x] = find(dsu[x]); 
    }  
    return dsu[x];  
} 
int n; 
long long cnt, ans; 
void kruskal() {
    init(); 
    std::sort(edge + 1, edge + 1 + cnt, cmp); 
    rep(i, 1, cnt) {
        int fx = find(edge[i].u); 
        int fy = find(edge[i].v); 
        if(fx != fy) {
            dsu[fx] = fy; 
            std::cout << edge[i].u << " " << edge[i].v << std::endl; 
        }   
    }
}

void solve() {
    std::cin >> n; 
    rep(i, 1, n) {
        std::cin >> c[i]; 
    }

    rep(i, 1, n) {
        for (int j = i * 2; j <= n; j += i) {
            cnt++; 
            edge[cnt].u = i; 
            edge[cnt].v = j; 
            if(c[i] == c[j]) {
                edge[cnt].w = -1; 
            } else {
                edge[cnt].w = 0; 
            }
        }
    }

    kruskal(); 
}

signed main() {
    IOS;
    solve(); 
    return 0; 
}

后续

老师说这题根本没有紫的难度！！！