POJ - 1251 Jungle Roads（最小生成树，Prim，Kruskal）

POJ - 1251 Jungle Roads

HDU - 1301 Jungle Roads

将字母转换成图，跑一遍Kruskal或者Prim就能求出最小生成树

Sample Input

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

Sample Output

216
30

Prim

#include<cstdio>
#include<cstring>
const int N = 110, INF = 0x3f3f3f3f;
int n;
int dis[N],book[N],e[N][N];
void Prim()
{
    memset(book,0,sizeof book);for(int i=1;i<=n;i++) dis[i]=e[1][i];book[1]=1;int ans=0;for(int i=1;i<=n-1;i++){
    int minn=INF,u;for(int j=1;j<=n;j++){
    if(!book[j]&&minn>dis[j]){
    u=j;minn=dis[j];}} book[u]=1;ans+=minn;for(int j=1;j<=n;j++)if(!book[j]&&dis[j]>e[u][j])dis[j]=e[u][j];} printf("%d\n",ans);
}
int main()
{
    char u,v;int m,w;while(scanf("%d",&n)&&n){
    memset(e,0x3f,sizeof e);for(int i=0;i<=n;i++) e[i][i]=0;for(int i=1;i<=n-1;i++){
    scanf(" %c %d",&u,&m);while(m--){
    scanf(" %c %d",&v,&w);e[u-'A'+1][v-'A'+1]=w;e[v-'A'+1][u-'A'+1]=w;}}Prim();}return 0;
}

Kruskal

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct note
{
    ll u,v,w;
}e[30*30];
int f[30];
int n,m,k;
bool cmp(note a,note b){
    return a.w<b.w;}
int find(int x) {
    return f[x]==x?x:find(f[x]);}
ll Kruskal()
{
    for(int i=0;i<=n;i++) f[i]=i;ll ans=0;for(int i=0;i<k;i++){
    int x=find(e[i].u);int y=find(e[i].v);if(x!=y){
    ans+=e[i].w;f[x]=y;}}return ans;
}
int main()
{
    char u,v;int w;while(cin>>n&&n){
    k=0;for(int i=1;i<n;i++)	{
    cin>>u>>m;while(m--){
    cin>>v>>w;e[k].u=u-'A'+1;e[k].v=v-'A'+1;e[k].w=w;k++;} }sort(e,e+k,cmp);cout<<Kruskal()<<endl;}return 0;
}