| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7753 | Accepted: 4247 |
Description
Input
Output
Sample Input
1 0 2 3 1 2 37 2 1 17 1 2 68 3 7 1 2 19 2 3 11 3 1 7 1 3 5 2 3 89 3 1 91 1 2 32 5 7 1 2 5 2 3 7 2 4 8 4 5 11 3 5 10 1 5 6 4 2 12 0
Sample Output
0 17 16 26
赤裸裸的最小生成树问题，下面用三种方式分别实现。
/* Kruskal 1287 Accepted 420K 16MS G++ */ #include"cstdio" #include"algorithm" using namespace std; const int MAXN=1000005; struct Edge{ int u,v,cost; }es[MAXN]; bool comp(const Edge &a,const Edge &b) { return a.cost < b.cost; } int par[MAXN]; int rnk[MAXN]; void init(int n) { for(int i=0;i<=n;i++) { par[i]=i; } } int fnd(int x) { if(par[x]==x) { return x; } return par[x]=fnd(par[x]); } void unite(int u,int v) { int a=fnd(u); int b=fnd(v); if(a==b) return ; if(rnk[a]<rnk[b]) { par[a]=b; } else{ par[b]=a; if(rnk[a]==rnk[b]) rnk[a]++; } } bool same(int u,int v) { return fnd(u)==fnd(v); } int main() { int V,E; while(scanf("%d",&V)!=EOF&&V) { scanf("%d",&E); for(int i=0;i<E;i++) { scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost); } sort(es,es+E,comp); init(V); int ans=0; int cnt=0; for(int i=0;i<E;i++) { if(!same(es[i].u,es[i].v)) { unite(es[i].u,es[i].v); ans+=es[i].cost; cnt++; } if(cnt==V-1) break; } printf("%d\n",ans); } return 0; }
/* Prim 1287 Accepted 408K 16MS G++ */ #include"cstdio" using namespace std; const int MAXN=105; const int INF=0x3fffffff; int mp[MAXN][MAXN]; int V,E; inline int min(int a,int b) { return a>b?b:a; } int d[MAXN]; int vis[MAXN]; int prim(int s) { int ans=0; for(int i=1;i<=V;i++) { d[i]=mp[s][i]; vis[i]=0; } d[s]=0,vis[s]=1; for(int i=1;i<=V-1;i++) { int mincost,k; mincost=INF; for(int i=1;i<=V;i++) { if(!vis[i]&&mincost>d[i]) { mincost=d[i]; k=i; } } vis[k]=1; ans+=mincost; for(int i=1;i<=V;i++) { if(!vis[i]&&d[i]>mp[k][i]) { d[i]=mp[k][i]; } } } return ans; } int main() { while(scanf("%d",&V)&&V) { for(int i=1;i<=V;i++) for(int j=1;j<=V;j++) if(i==j) mp[i][j]=0; else mp[i][j]=INF; scanf("%d",&E); for(int i=0;i<E;i++) { int u,v,co; scanf("%d%d%d",&u,&v,&co); mp[u][v]=mp[v][u]=min(mp[u][v],co); } printf("%d\n",prim(1)); } return 0; }
/* 堆优化prim 1287 Accepted 604K 16MS G++ */ #include"cstdio" #include"cstring" #include"queue" using namespace std; const int MAXN=10005; const int INF=0x3fffffff; struct Edge{ int to,cost,next; }es[MAXN]; struct Node{ int d,u; Node(int cd,int cu):d(cd),u(cu){ } bool operator<(const Node& a) const { return d > a.d; } }; int V,E; int head[105]; int cnt; void add_edge(int u,int v,int co) { es[cnt].to=v; es[cnt].cost=co; es[cnt].next=head[u]; head[u]=cnt; cnt++; } int d[105]; int vis[105]; int prim(int s) { int ans=0; for(int i=1;i<=V;i++) { vis[i]=0; d[i]=INF; } d[s]=0; priority_queue<Node> que; que.push(Node(0,s)); while(!que.empty()) { Node no=que.top();que.pop(); int v=no.u; if(vis[v]) continue; ans+=no.d; vis[v]=1; for(int i=head[v];i!=-1;i=es[i].next) { Edge e=es[i]; if(d[e.to]>e.cost) { d[e.to]=e.cost; que.push(Node(d[e.to],e.to)); } } } return ans; } int main() { while(scanf("%d",&V)&&V) { cnt=0; memset(head,-1,sizeof(head)); scanf("%d",&E); for(int i=0;i<E;i++) { int u,v,co; scanf("%d%d%d",&u,&v,&co); add_edge(u,v,co); add_edge(v,u,co); } int ans=prim(1); printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5155688.html