首页 > 代码库 > poj1251--Kruskal
poj1251--Kruskal
/* * poj1251-- Kruskal * date 2014/7/15 * state AC */ #include <iostream> #include <algorithm> #include <fstream> #include <cstdio> #include <cstring> using namespace std; int const MAXN=30+100; int u[MAXN]; int v[MAXN]; int w[MAXN+50]; int p[MAXN]; int r[MAXN]; int cmp(const int i,const int j) { return w[i]<w[j]; } int unionFindSet(int x) { return p[x]==x?x:p[x]=unionFindSet(p[x]); } int Kruskal(int n,int m) { int ans=0; //memset(p,0,sizeof(p)); //memset(r,0,sizeof(r)); for(int i=0;i<n;i++) p[i]=i; for(int i=0;i<m;i++) r[i]=i; //mem sort(r,r+m,cmp); for(int i=0;i<m;i++) { int e=r[i]; int x=unionFindSet(u[e]); int y=unionFindSet(v[e]); if(x!=y) { ans+=w[e]; p[x]=y; } } return ans; } int main() { //cout << "Hello world!" << endl; //freopen("input.txt","r",stdin); char a[2],b[2]; int c; int m; int n; int edgeNum; while(scanf("%d",&n)) { if(n==0)break; memset(u,0,sizeof(u)); memset(v,0,sizeof(v)); memset(w,0,sizeof(w)); edgeNum=0; for(int i=0;i<n-1;i++) { scanf("%s%d",a,&m); for(int j=0;j<m;j++) { scanf("%s%d",b,&c); u[edgeNum]=a[0]-'A'; v[edgeNum]=b[0]-'A'; w[edgeNum]=c; edgeNum++; } } // /*cout<<"edgeNumber: "<<edgeNum<<endl; for(int k=0;k<edgeNum;k++) cout<<u[k]<<" "<<v[k]<<" "<<w[k]<<" "; cout<<"---"<<endl; */ cout<<Kruskal(n,edgeNum)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。