学步园

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1013

最小生成树 代码

#include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> #define MAX 5003<br /> int u[MAX],v[MAX],w[MAX],p[MAX],r[MAX];<br /> int n;<br /> void init(){<br /> int i,j;int m=0;int ss;<br /> for(i=0;i<n;++i){<br /> for(j=0;j<n;++j)<br /> if(i>j){<br /> u[m]=i;v[m]=j;<br /> cin>>w[m];m++;<br /> }<br /> else cin>>ss;<br /> }<br /> }<br /> int cmp(const int i,const int j){<br /> return w[i]<w[j];<br /> }<br /> int find(int x){<br /> return p[x]==x?x:p[x]=find(p[x]);<br /> }<br /> int kruskal(){<br /> int ans=0;int i;int m=(n*n-n)/2;<br /> for(i=0;i<n;++i)p[i]=i;<br /> for(i=0;i<m;++i)r[i]=i;<br /> sort(r,r+m,cmp);<br /> for(i=0;i<m;++i){<br /> int e=r[i];int x=find(u[e]),y=find(v[e]);<br /> if(x!=y){<br /> ans+=w[e];p[x]=y;<br /> }<br /> }return ans;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> while(cin>>n){<br /> init();<br /> cout<<kruskal()<<endl;<br /> }<br /> return 0;<br /> }<br />