题解
这是一道裸的最小生成树题，拿来练手，题目就不放了
个人理解 Prim有些类似最短路和贪心，不断找距当前点最小距离的点
Kruskal类似于并查集，不断找最小的边，如果不是一棵树的节点就合并为一颗树
AC代码：
Prim算法：
#include<iostream>
#include<cstdio> //EOF,NULL
#include<cstring> //memset
#include<cstdlib> //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
#include<cmath> //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
#include<algorithm> //fill,reverse,next_permutation,__gcd,
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<iterator>
#include<iomanip> //setw(set_min_width),setfill(char),setprecision(n),fixed,
#include<functional>
#include<map>
#include<set>
#include<limits.h> //INT_MAX
#include<bitset> // bitset<?> n
using namespace std; typedef long long ll;
typedef pair<int,int> P;
#define all(x) x.begin(),x.end()
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
const int INF =0x3f3f3f3f;
const int inf =0x3f3f3f3f;
const int mod = 1e9+;
const int MAXN = ;
const int maxn = ;
int n,m,v;
int pos,imin ;
int ans ;
char a,b ;
int vis[MAXN],dis[MAXN];
int mapp[MAXN][MAXN];
void Init(){
mst(vis,);
ans = ;
for(int i = ;i < n; i++) dis[i] = inf;
for(int i = ;i < n; i++)
for(int j = ; j < n; j++){
if(i == j) mapp[i][j] = ;
else mapp[i][j] = inf;
}
}
void prim(){
for(int i = ; i < n ; i++)
dis[i] = mapp[][i];
dis[] = ;
vis[] = ;
for(int i = ; i < n ; i ++) {
pos = ;
imin = inf;
for(int j = ; j < n ; j++ )
if(!vis[j] && dis[j] < imin) pos = j , imin = dis[j];
vis[pos] = ;
ans += imin ;
for(int j = ; j < n; j++)
if(!vis[j] && mapp[pos][j] < dis[j]) dis[j] = mapp[pos][j];
}
}
int main(){
while(cin >> n && n){
Init();
for(int i = ; i < n; i++){
cin >> a >> m ;
int st = a -'A';
while(m--) {
cin >> b >> v ;
int ed = b - 'A';
mapp[st][ed] = v;
mapp[ed][st] = v;
}
}
prim();
print(ans);
}
return ;
}
Kruskal算法：
#include<iostream>
#include<cstdio> //EOF,NULL
#include<cstring> //memset
#include<cstdlib> //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
#include<cmath> //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
#include<algorithm> //fill,reverse,next_permutation,__gcd,
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<iterator>
#include<iomanip> //setw(set_min_width),setfill(char),setprecision(n),fixed,
#include<functional>
#include<map>
#include<set>
#include<limits.h> //INT_MAX
#include<bitset> // bitset<?> n
using namespace std; typedef long long ll;
typedef pair<int,int> P;
#define all(x) x.begin(),x.end()
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
const int INF =0x3f3f3f3f;
const int inf =0x3f3f3f3f;
const int mod = 1e9+;
const int MAXN = ;
const int maxn = ; struct node{
int st,ed,v;
bool operator < (node b) const{
return v < b.v;
}
}rod[MAXN];
int n,m;
int cnt,ans;
int pre[MAXN]; int find(int x){ return x == pre[x] ? x : pre[x] = find(pre[x]);}
bool join(int x,int y){
if(find(x)!=find(y)){
pre[find(y)] = find(x);
return true;
}
return false;
}
void Init(){
ans = ;
cnt = ;
for(int i = ; i < MAXN ; i++){
pre[i] = i;
}
}
void kruskal(){
for(int i = ;i < cnt ; i++){
int mp1 = find(rod[i].st);
int mp2 = find(rod[i].ed);
if(join(mp1,mp2)) ans+= rod[i].v;
}
}
int main(){
while(cin >> n && n){
Init();
char a,b ;
int m,v;
for(int i = ; i < n; i++){
cin >> a >> m ;
int st = a -'A';
while(m--) {
cin >> b >> v ;
int ed = b - 'A';
rod[cnt].st = st;
rod[cnt].ed = ed;
rod[cnt++].v = v;
}
}
sort(rod,rod+cnt);
kruskal();
print(ans);
}
return ;
}