刷题刷到自闭，写个博客放松一下

题意：n个人，m对朋友，每寻找一个人传播消息需要花费相应的价钱，朋友之间传播消息不需要花钱，问最小的花费

把是朋友的归到一起，求朋友中花钱最少的，将所有最少的加起来。

1 #include
2 #include
3 #include
4 #define ll long long
5 using namespace std;
6
7 ll a[1000100];
8
9 struct lll
10 {
11 ll par,b,c;
12 }p[100100];
13
14 int cmp(lll x,lll y)
15 {
16 if(x.par==y.par) return x.b<y.b;
17 return x.par<y.par;
18 }
19
20 ll find(ll x)
21 {
22 if(x!=p[x].par) p[x].par=find(p[x].par);
23 return p[x].par;
24 }
25
26 void unionn(ll x,ll y)
27 {
28 ll fa=find(x);
29 ll fb=find(y);
30 if(fb==fa) return ;
31 if(p[fa].c<p[fb].c){
32 p[fa].par=fb;
33 }
34 else p[fb].par=fa;
35 if(p[fa].c==p[fb].c) p[fa].c++;
36 }
37
38 int main()
39 {
40 ll n,m;
41 while(scanf("%lld%lld",&n,&m)!=EOF){
42 memset(a,0,sizeof a);
43 memset(p,0,sizeof p);
44 for(ll i=1;i<=n;i++){
45 scanf("%lld",&a[i]);
46 p[i].par=i;
47 p[i].b=a[i];
48 p[i].c=0;
49 }
50 ll x,y;
51 for(ll i=0;i<m;i++){
52 scanf("%lld%lld",&x,&y);
53 unionn(x,y);
54 }
55 ll sum=0;
56 for(int i=1;i<=n;i++)
57 while(p[i].par!=i&&p[p[i].par].par!=p[i].par) //是同一类但是头不是老大 把头变为老大；
58 p[i].par=p[p[i].par].par;
59 sort(p+1,p+n+1,cmp); //把结构体按类排序，主要是同一类的花费少的在前
60 sum=p[1].b;
61 for(int i=2;i<=n;i++){
62 if(p[i].par!=p[i-1].par) sum+=p[i].b; //是同一类的加上花费最少的第一个 不是同一类就继续循环
63 }
64 printf("%lld\n",sum);
65 }
66 return 0;
67 }