洛谷 P1194 买礼物

题目传送门

2019.8.7,Mr^Simon蒟蒻水题T1
解题思路:

最小生成树的裸题.
AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm> 
 4 
 5 using namespace std;
 6 
 7 int a,b,v,tot,fa[501],cnt,ans;
 8 struct kkk {
 9     int from,to,v;
10 }e[250001]; 
11 
12 bool cmp(kkk a,kkk b) {
13     return a.v < b.v;
14 }
15 
16 int find_father(int x) {
17     if(fa[x] == x) return x;
18     return fa[x] = find_father(fa[x]);
19 }
20 
21 int main()
22 {
23     scanf("%d%d",&a,&b);
24     for(int i = 0;i <= b; i++) fa[i] = i;
25     for(int i = 1;i <= b; i++) {
26         e[++tot].from = 0;
27         e[tot].to = i;
28         e[tot].v = a;    
29         for(int j = 1;j <= b; j++) {
30             scanf("%d",&v);
31             if(v != 0) {
32                 e[++tot].from = i;
33                 e[tot].to = j;
34                 e[tot].v = v;
35             }
36         }
37     }
38     if(b == 1) {
39         printf("%d",a);
40         return 0;
41     }
42     sort(e+1,e+1+tot,cmp);
43     for(int i = 1;i <= tot; i++) {
44         int x1 = find_father(e[i].from);
45         int y1 = find_father(e[i].to);
46         if(x1 != y1) {
47             ans += e[i].v;
48             fa[x1] = y1;
49             cnt++;
50         }
51         if(cnt == b - 1) {
52             printf("%d",ans + a);
53             return 0;
54         }
55     }
56     return 0;
57 }