很简单的最小生成树，有两种做法，我采用Kruskal和Prim都试了一下。一种是使已经有的边距离为0，这样既能顺利地生成，又能不影响答案；第二种是合并已经有的两条边的集合。我这里kruskal采用的是第二种方法，Prim只能用第一种方法。
Kruskal Algorithm Code：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 107 int mp[N][N],fa[N],vis[N][N],n,res; struct Edge { int s,t,w; }edge[N*N]; int cmp(Edge ka,Edge kb) { return ka.w < kb.w; } int findset(int x) { if(x != fa[x]) fa[x] = findset(fa[x]); return fa[x]; } void Kruskal() { int i,j,k = 0,q,A,B; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { edge[k].s = i; edge[k].t = j; edge[k].w = mp[i][j]; k++; } } sort(edge,edge+k,cmp); for(i=1;i<=n;i++) fa[i] = i; res = 0; scanf("%d",&q); for(i=0;i<q;i++) { scanf("%d%d",&A,&B); int u = findset(A); int v = findset(B); fa[u] = v; } for(i=0;i<k;i++) { int u = edge[i].s; int v = edge[i].t; int fx = findset(u); int fy = findset(v); if(fx != fy) { res += edge[i].w; fa[fx] =fy; } } } int main() { int i,j; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&mp[i][j]); Kruskal(); printf("%d\n",res); } return 0; }
Prim Algorithm Code：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define Mod 1000000007 using namespace std; #define N 107 int mp[N][N],vis[N],n,res,len[N]; void Prim() { int i,j,k,mini; res = 0; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) len[i] = mp[1][i]; len[1] = 0; vis[1] = 1; for(i=1;i<=n;i++) { mini = Mod; for(j=1;j<=n;j++) { if(!vis[j] && len[j] < mini) { mini = len[j]; k = j; } } if(mini == Mod) return; res += len[k]; vis[k] = 1; for(j=1;j<=n;j++) { if(!vis[j] && len[j] > mp[k][j]) len[j] = mp[k][j]; } } } int main() { int i,j,q,u,v; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&mp[i][j]); scanf("%d",&q); while(q--) { scanf("%d%d",&u,&v); mp[u][v] = mp[v][u] = 0; } Prim(); printf("%d\n",res); } return 0; }
HDU 1102 Constructing Roads,布布扣,bubuko.com
原文：http://www.cnblogs.com/whatbeg/p/3626119.html
