hdu 1233 还是畅通工程

prim实现 #include<iostream>#include<string>#define MAXINT 9999999using namespace std;int map[101][101],s[101],dis[101],n;int prim(){int sum=0; memset(s,0,sizeof(s)); s[1]=1;for(int i=2;i<=n;i++) dis[i]=map[1][i]; dis[1]=0;for(int i=1;i<n;i++) {int min=MAXINT,k=1;for(int j=1;j<=n;j++)if(!s[j]&&dis[j]<min) k=j,min=dis[j]; sum+=min; s[k]=1;for(int j=1;j<=n;j++) { min=map[k][j];if(min<dis[j]) dis[j]=min; } }return sum;}int main(){int a,b,c;while(scanf("%d",&n)==1&&n) {int m=(n*(n-1))/2;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) map[i][j]=MAXINT;for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&c);if(map[a][b]>c) { map[a][b]=c; map[b][a]=c; } } cout<<prim()<<endl; }return 0;}

Kruskal 相对而言快了很多，用并查集实现

我写了俩个，不过效率相差太大了

Kruskal算法 #include<iostream>#include<string>#define MAXN 101using namespace std;int n,m,f[MAXN],ans;struct edge{int u,v,w; edge(int x=0,int y=0,int z=0):u(x),v(y),w(z){};}e[MAXN*50];int cmp(const void *a, const void *b) { if(((struct edge *)a)->w!=((struct edge *)b)->w) {return ((struct edge *)a)->w-((struct edge *)b)->w; }else {return ((struct edge *)a)->u-((struct edge *)b)->u; }} void init(){for(int i=0;i<=n;i++) f[i]=i;}int find(int x){if(x==f[x])return x; f[x]=find(f[x]);return f[x];}void Union(int x,int y,int c){int a=find(x);int b=find(y);if(a==b)return ; f[b]=a; ans+=c;}int main(){int a,b,c;while(scanf("%d",&n)==1&&n) { m=(n*(n-1))/2;int num=0;for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&c); e[num++]=edge(a,b,c); } qsort(e,num,sizeof(e[0]),cmp); init(); ans=0;for(int i=0;i<num;i++) Union(e[i].u,e[i].v,e[i].w); printf("%d\n",ans); }return 0;}

 

转载于:https://www.cnblogs.com/nanke/archive/2011/08/15/2139999.html

相关资源：数据结构—成绩单生成器