luogu P1196 [NOI2002]银河英雄传说

www

在用反集混过了团伙以及食物链两道题后

我终于还是写了带权并查集emmmm

（题干令人头大预警

（对没错我就没好好看题干先写了读入233333

（挺好懂其实

好哒看完题啦

那我们放代码吧【开玩笑的 

 emmmmm

就是，在每次路径压缩的时候，也要更新一下子节点到父节点的距离

然后同时这道题还要更新每列的战舰个数

嗯对

放代码（草率了事

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 30010

int fa[maxn];
int dis[maxn];
int num[maxn];

int find(int x) {
    if(x == fa[x])
        return x;
    int f = fa[x];//记一下fa[x]
    fa[x] = find(fa[x]);
    dis[x] += dis[f];//更新距离
    return fa[x];
}

void add(int x,int y) {
    int a = find(x);
    int b = find(y);//找到父节点
    dis[a] += num[b];//嗯还是更新距离
    fa[a] = b;//并起来
    num[b] += num[a];//把当前这一列的战舰数增加
    num[a] = 0;//被挪过来的那一列理所当然地变成0艘战舰
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= 30010; i++) {
        num[i] = 1;//每列都只有一艘
        fa[i] = I;//初始化
    }
    for(int k = 1; k <= n; k++) {
        char ch;
        int i,j;
        cin >> ch >> i >> j;
        if(ch == 'M')
            add(i,j);
        else {
            if(find(i) == find(j))
                printf("%d
",abs(dis[i] - dis[j]) - 1);//减一en
            else
                printf("-1
");
        }
    }
    return 0;
}

假装讲的很详细

但其实什么都没讲（这你还敢放？？？

【告辞