文章

13

粉丝

386

获赞

2

访问

65.7k

头像
并查集+Kruskal
P1311 浙江大学机试题
发布于2022年3月6日 13:47
阅读数 4.6k

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1000 + 10;

struct Edge{
    int from, to, length, statue;
    Edge(int f, int t, int l, int s): from(f), to(t), length(l), statue(s){}
    bool operator>(const Edge &e) const{
        if(statue == e.statue) return length > e.length;
        return statue < e.statue;
    }
};
int arr[N];

void Initial(){
    fill(arr, arr + N, -1);
}

int Find(int x){
    int root = x;
    while(arr[root] > 0) root = arr[root];
    while(x != root){
        int t = arr[x];
        arr[x] = root;
        x = arr[x];
    }
    return root;
}

bool Union(int x, int y){
    int root1 = Find(x);
    int root2 = Find(y);
    if(root1 != root2){
        if(arr[root1] < arr[root2]){
            arr[root1] += arr[root2];
            arr[root2] = root1;
        }else{
            arr[root2] += arr[root1];
            arr[root1] = root2;
 ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发