POJ1251（最小生成树kruskal算法+prim算法两种解决）

1.注意输入：scanf()函数输入的时候，%s比%c使用起来更加方便，因为%s不需要考虑空格和换行符的问题

2.注意最小生成树算法，kruskal算法适用于稀疏图，算法复杂度O(e*log(e))e为图的边数，和顶点数无关 

第一种：kruskal算法 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{int from;int to;int weight;
} pp[80];
int pre[30];
int n;
char x,h;
int m,qq,ans,w;
void init()
{qq=0;ans=0;for(int i=0; i<30; i++)pre[i]=i;
}
int finds(int x)
{if(pre[x]==x)return pre[x];pre[x]=finds(pre[x]);return pre[x];
}
bool cmp(node a,node b)
{return a.weight<b.weight;
}
void kruskal()
{sort(pp,pp+qq,cmp);for(int i=0; i<qq; i++){int from=finds(pp[i].from);int to=finds(pp[i].to);if(from!=to)//两点的在不同的连通图时{pre[from]=to;ans+=pp[i].weight;}}
}
int main()
{while(scanf("%d",&n)&&n){init();for(int i=0; i<n-1; i++){scanf("%s%d",&x,&m);for(int j=0; j<m; j++){scanf("%s%d",&h,&w);pp[qq].from=x-'A';pp[qq].to=h-'A';pp[qq++].weight=w;}}kruskal();printf("%d\n",ans);}return 0;
}

 第二种：prim算法：时间复杂度O(n^2)，因此适用于稠密图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30;
const int inf=0x3f3f3f;
int mapp[maxn][maxn];
int dis[maxn];
int vis[maxn];
int n;
char x,h;
int m,ans,w;
void init()
{ans=0;memset(vis,0,sizeof(vis));memset(mapp,inf,sizeof(mapp));
}
void prim()
{for(int i=0; i<n; i++){dis[i]=mapp[0][i];}dis[0]=0;vis[0]=1;for(int v=0; v<n-1; v++){int minx=inf;int p=-1;for(int i=0; i<n; i++)if(!vis[i]&&dis[i]<minx){p=i;minx=dis[i];}ans+=dis[p];vis[p]=1;for(int i=0; i<n; i++)if(!vis[i]&&dis[i]>mapp[p][i])dis[i]=mapp[p][i];}
}
int main()
{while(scanf("%d",&n)&&n){init();for(int i=0; i<n-1; i++){scanf("%s%d",&x,&m);for(int j=0; j<m; j++){scanf("%s%d",&h,&w);int from=x-'A';int to=h-'A';mapp[from][to]=mapp[to][from]=w;}}prim();printf("%d\n",ans);}return 0;
}