代码一:普里母算法 #include<stdio.h> int map[101][101]; int visit[101]; int prim(int n); int main() { int n,m,a,b,i,j; while(~scanf("%d",&n)) { for(i=1;i<=n;++i) { visit[i]=0; for(j=1;j<=n;++j) scanf("%d",&map[i][j]); } scanf("%d",&m); for(i=1;i<=m;++i) { scanf("%d%d",&a,&b); map[a][b]=map[b][a]=0; } printf("%d\n",prim(n)); } } int prim(int n) { int i,j,k,min,tot=0; int dis[101]; for(i=1;i<=n;++i) dis[i]=map[1][i]; visit[1]=1; for(i=2;i<=n;++i) { min=0x7fffffff; k=1; for(j=1;j<=n;++j) { if(!visit[j]&&min>dis[j]) { min=dis[j]; k=j; } } visit[k]=1; tot+=dis[k]; for(j=1;j<=n;++j) if(!visit[j]&&map[k][j]<dis[j]) dis[j]=map[k][j]; } return tot; } //代码二:克鲁斯卡尔算法(转) #include <iostream> #include <algorithm> #define MAX 200 using namespace std; int father[MAX]; int my_rank[MAX]; void make_set() { for (int i = 0; i < MAX; i++) { father[i] = i; my_rank[i] = 0; } } int find_set(int x) { if (x != father[x]) father[x] = find_set(father[x]); return father[x]; } void union_set(int x, int y) { x = find_set(x); y = find_set(y); if (x == y) return; if (my_rank[x] > my_rank[y]) father[y] = x; else { father[x] = y; if (my_rank[x] == my_rank[y]) my_rank[y]++; } } struct edge { int start; int end; int weight; }; bool cmp(const edge& a, const edge& b) { return a.weight < b.weight; } edge e[99*50+2]; int main() { int N, Q, count; int x, y, cost; while (cin >> N) { count = 0; make_set(); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cin >> cost; if (j > i) { e[count].start = i; e[count].end = j; e[count++].weight = cost; } } } cin >> Q; for (int i = 0; i < Q; i++) { cin >> x >> y; x = find_set(x); y = find_set(y); if (x != y) union_set(x, y); } sort(e, e+count, cmp); N = count; count = 0; int sum = 0; while (count != N) { x = find_set(e[count].start); y = find_set(e[count].end); if (x != y) { union_set(x, y); sum += e[count].weight; } count++; } cout << sum << endl; } return 0; }
HDOJ1102 Constructing Roads
功不成,身已退