Jungle Roads
Prime算法
#include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; #define INF 99999 typedef long long int ll ; int n; int v[101][101]; int vis[101]={0},cost[101]; void prim(){ for (int i = 0; i < n; ++i) { cost[i] = v[0][i]; vis[0] = 0; } vis[0] = 1; cost[0] = 0; for (int i = 1; i < n; ++i) { int min = INF,k = -1; for (int j = 0; j < n; ++j) { if(!vis[j]&& min>cost[j]){ min = cost[j]; k = j; } } if(k == -1) break; vis[k] = 1; for (int j = 0; j < n; ++j) { if(v[k][j]<cost[j]&&!vis[j]){ cost[j] = v[k][j]; } } } ll sum = 0; for (int i = 1; i < n; ++i) { sum += cost[i]; } cout<<sum<<endl; } int main(int argc, char const *argv[]) { while(1){ cin>>n; if(n == 0) break; fill(v[0],v[0]+101*101,INF); for (int i = 0; i < n-1; ++i) { char s; cin>>s; int N; cin>>N; for (int j = 0; j < N; ++j) { char k; int t; cin>>k>>t; v[s-'A'][k-'A'] = t; v[k-'A'][s-'A'] = t; } } prim(); } return 0; }kruskal算法：
#include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; struct edge { int u,v,w; }e[101]; int n; int fa[101]; bool com(edge a,edge b){ return a.w < b.w; } int find(int x){ if(x == fa[x]){ return x; } return fa[x] = find(fa[x]); } void init(){ for (int i = 0; i < n; ++i) { fa[i] = i; } } int main(){ while(1){ cin>>n; if(n == 0) break; int m = 0; for (int i = 0; i < n-1; ++i) { char s; int t; cin>>s>>t; for (int j = 0; j < t; ++j) { char k; int l; cin>>k>>l; e[m].u = s-'A'; e[m].v = k-'A'; e[m++].w = l; } } sort(e,e+m,com); init(); int sum = 0; for (int i = 0; i < m; ++i) { int xx = find(e[i].u); int yy = find(e[i].v); if(xx != yy){ sum += e[i].w; fa[xx] = yy; } } cout<<sum<<endl; } }