Jungle Roads 两种最小生成树

最小生成树的两种算法
Prim；

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int map[121][121];
int book[121];
int dis[121];
int n,inf=9999999;
void Prim()
{
    int i,j,u;memset(book, 0, sizeof(book));//printf("%d\n",n);for(int i=1; i<=n; i++){
    dis[i] = map[1][i];// printf("%d\n",dis[i]);}book[1] = 1;int sum= 0;for(int i=1; i<=n; i++){
    int minn = inf;for(int j=0; j<=n; j++){
    if(dis[j]<minn&&!book[j]){
    minn = dis[j];u = j;}}sum += minn;book[u] = 1;for(int j=0; j<=n; j++){
    if(map[u][j]<dis[j]&&book[j]==0){
    dis[j] = map[u][j];}}}printf("%d\n", sum);
}
int main()
{
    int a, b, f, e;char c, d;while(~scanf("%d", &n)&&n){
    memset(map,inf,sizeof(map));for(int i=1;i<n;i++){
    scanf("\n%c",&c);a=c-'A'+1;scanf("%d",&f);for(int j=0;j<f;j++){
    scanf("\n%c %d",&d,&e);b=d-'A'+1;map[a][b]=map[b][a]=e;}}Prim();}return 0;
}

kruskal

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,dot,inf=9999999;
int pre[150];
struct node
{
    int u;int v;int cost;
}p[5002];
int find(int x)
{
    if(pre[x]==x)return x;else{
    pre[x]=find(pre[x]);return pre[x];}
}
bool cmp(node x,node y)
{
    return x.cost<y.cost;
}
int main()
{
    int i,j;char a,b,c[150],d;while(~scanf("%d",&n)&&n){
    for(i=0;i<n;i++){
    pre[i]=i;}int size=0,t,co;for(i=1;i<n;i++){
    scanf("\n%c %d",&a,&t);for(j=0;j<t;j++){
    scanf("\n%c %d",&b,&co);p[size].u=a-'A';p[size].v=b-'A';p[size].cost=co;size++;}}sort(p,p+size,cmp);int ans=0;for(i=0;i<size;i++){
    int r1=find(p[i].u);int r2=find(p[i].v);if(r1!=r2){
    pre[r1]=r2;ans+=p[i].cost;}}printf("%d\n",ans);}return 0;
}