题目链接 http://poj.org/problem?id=1251
本题主要是来求解最小生成树
通过并查集来对每一个节点进行存取 (此时节点已经排序根据权值大小)
以下是代码
- #include<iostream>
- #include<vector>
- #include<algorithm>
- #define MAX_N 150
- using namespace std;
- int pre[MAX_N];
- int n;
- char c[MAX_N],c1[MAX_N];
- int finds(int x)
- {
- return x==pre[x]?x:finds(pre[x]);
- }
- void unions(int x, int y)
- {
- int find_x=finds(x);
- int find_y=finds(y);
- if(find_x==find_y)
- return;
- pre[find_x]=find_y;
- }
- bool Judge(int x, int y)
- {
- return finds(x)==finds(y);
- }
- struct Pit
- {
- int l,r,w;
- } p;
- vector<Pit> V;
- bool cmp(Pit p1,Pit p2)
- {
- return p1.w<p2.w;
- }
- int main()
- {
- while(cin>>n)
- {
- V.clear();
- if(n==0) break;
- for(int i=0; i<n; i++)
- {
- pre[i]=i;
- }
- for(int i=0; i<n-1; i++)
- {
- int a;
- cin>>c>>a;
- for(int i=0; i<a; i++)
- {
- int b;
- cin>>c1>>b;
- p.l=c[0]-A;
- p.r=c1[0]-A;
- p.w=b;
- V.push_back(p);
- }
- }
- int ans=0;
- sort(V.begin(),V.end(),cmp);
- for(int i=0; i<V.size(); i++)
- {
- if(Judge(V[i].l,V[i].r))
- continue;
- ans+=V[i].w;
- unions(V[i].l,V[i].r);
- }
- cout<<ans<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2522636.html