OI

【并查集】修复公路

P1111
虽然第一反应是最小生成树，但是不会（

于是并查集。设置每个节点除了记录父节点外，记录当前子树的节点数（即子集合的元素数），最大的集合元素数等于n时，即合并完毕。

可是又TLE了好几次，所以这里要总结一个经验：反复调用的函数不要开局部数组，很费时间，能全局量/传指针就不要开局部量（尽管挺影响可读性，为了效率……）最大一个点36ms，比较理想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#define MAX 100005
struct node{
    int x,y,t;
};
struct node queue[MAX];
struct tree{
    int father,num;
};
struct tree map[MAX];
int t[MAX]={0};
int maxnum=0;
int fx,fy;
void qqsort(int l,int r){
    int i,j,mid;
    struct node t;
    i=l;
    j=r;
    mid=queue[(i+j)/2].t;
    do{
        while(queue[i].t<mid)i++;
        while(queue[j].t>mid)j--;
        if(i<=j){
            t=queue[i];
            queue[i]=queue[j];
            queue[j]=t;
            i++;
            j--;
        }
    }while(i<=j);
    if(i<r)qqsort(i,r);
    if(l<j)qqsort(l,j);
}

int find(int x){
    int k=0,i;
    while(map[x].father!=x){
        k++;
        t[k]=x;
        x=map[x].father;
    }
    for(i=1;i<=k-1;i++)
        map[t[i]].father=x; 
    return x;
}

void unite(){
    map[fx].num+=map[fy].num;
    if(maxnum<map[fx].num)maxnum=map[fx].num;
    map[fy].father=fx;
}

int vis(int x,int y){
    fx=find(x);
    fy=find(y);
    if(fx==fy)return 1;
    return 0;
}

int main(){
    int n,m,i,x,y,t,ans=0,f=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&queue[i].x,&queue[i].y,&queue[i].t);
        map[i].father=i;
        map[i].num=1;
    }
    qqsort(1,m);

    for(i=1;i<=m;i++){
        x=queue[i].x;
        y=queue[i].y;
        if(!vis(x,y)){
            ans=queue[i].t;
            unite();
        }
        if(maxnum==n){
            printf("%d",ans);
            f=0;
            break;
        }
        
    }
    if(f)printf("-1");
    return 0;
}