学步园

题目链接：气点

/*
  Nyoj 434 Jungle Rode
  Kruscal 写的.算是裸的最下生成树吧！
  输入上有点坑,cin过的。
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=30;
const int MAX=250;
struct Island
{
    int x,y;
    int len;
}island[MAX];
bool cmp(Island a,Island b)
{
    if(a.len<b.len) return true;
    return false;
}
int n,top,father[N];
void intput()
{
    char c;
    int LNum;
    top=0;
    for(int i=1;i<n;i++)
    {
        cin>>c>>LNum;
        int temp;
        char ctemp;
        for(int j=1;j<=LNum;j++)
        {
            cin>>ctemp>>temp;
            island[top].x=c-'A'+1;
            island[top].y=ctemp-'A'+1;
            island[top].len=temp;
            top++;
        }
        getchar();
    }
}
int Find_Father(int x)
{
    if(x!=father[x])
    father[x]=Find_Father(father[x]);
    return father[x];
}
void kruscal()
{
    int min=0;
    for(int i=0;i<=N;i++)
    father[i]=i;
    sort(island,island+top,cmp);
    for(int i=0;i<top;i++)
    {
        int a=Find_Father(island[i].x);
        int b=Find_Father(island[i].y);
        if(a!=b)
        {
            father[a]=b;
            min+=island[i].len;
        }
    }
    printf("%d\n",min);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        getchar();
        intput();
        kruscal();
    }
}
/*
  kruscal小小的模板
*/
const int N=?
const int MAX=?
struct Rode
{
    int xpoint,ypoint;
    int lenth;
}rode[MAX];
void Init()
{
    for(int i=0;i<N;i++)
    father[i]=i;
}
int Find_Father(int x)
{
    if(x!=father[x])
    father[x]=Find_Father(father[x]);
    return father[x];
}
int Kruscal()
{
    int min=0;
    Init();
    for(int i=0;i<=MAX;i++)
    {
        int a=Find_Father(rode[i].xpoint);
        int b=Find_Father(rode[i].ypoint);
        if(a!=b)
        {
            father[a]=b;
            min+=rode[i].lenth;
        }
    }
    return min;
}

还需要用量变到质变，多做题。