POJ-1287 Networking---裸的不能再裸的MST

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<sstream>10 using namespace std;11 typedef long long ll;12 const int maxn = 3e5 + 10;13 const int INF = 1 << 30;14 int dir[4][2] = {1,0,0,1,-1,0,0,-1};15 int T, n, m, x;16 struct edge17 {18 ????int u, v, w;19 ????bool operator <(const edge& a)const20 ????{21 ????????return w < a.w;22 ????}23 };24 edge a[maxn];25 int par[600], high[600];26 //初始化n个元素27 void init(int n)28 {29 ????for(int i = 0; i < n; i++)30 ????{31 ????????par[i] = i;32 ????????high[i] = 0;33 ????}34 }35 //查询树的根36 int Find(int x)37 {38 ????return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩39 }40 void unite(int x, int y)41 {42 ????x = Find(x);43 ????y = Find(y);44 ????if(x == y)return;45 ????if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y46 ????else47 ????{48 ????????par[y] = x;49 ????????if(high[x] == high[y])high[x]++;50 ????}51 }52 bool same(int x, int y)53 {54 ????return Find(x) == Find(y);55 }56 void kruskal(int n, int m)//点数n，边数m57 {58 ????int sum_mst = 0;//mst权值59 ????int num= 0;//已经选择的边的边数60 ????sort(a, a + m);//边进行排序61 ????init(n);//初始化并查集62 ????for(int i = 0; i < m; i++)63 ????{64 ????????int u = a[i].u;65 ????????int v = a[i].v;66 ????????if(Find(u - 1) != Find(v - 1))//图最开始的下标是1，并查集是067 ????????{68 ????????????//printf("%d %d %d\n", u, v, a[i].w);69 ????????????sum_mst += a[i].w;70 ????????????num++;71 ????????????unite(u - 1, v - 1);72 ????????}73 ????????if(num >= n - 1)break;74 ????}75 ????//printf("weight of mst is %d\n", sum_mst);76 ????cout<<sum_mst<<endl;77 }78 int main()79 {80 ????while(cin >> n && n)81 ????{82 ????????cin >> m;83 ????????for(int i = 0; i < m; i++)84 ????????{85 ????????????cin >> a[i].u >> a[i].v >> a[i].w;86 ????????}87 ????????kruskal(n, m);88 ????}89 ????return 0;90 }