学步园

题目链接：击点

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 105
#define Max 6000
#define MAX 10000
using namespace std;
int Map[N][N],nodeset[N];
bool vis[N];
struct Rode
{
    int x,y,w;
}r[Max];
bool cmp(Rode a,Rode b)
{
    if(a.w<b.w) return true;
    return false;
}
int Kruscal(int n,int k)
{
    int top=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i<j)
            {
                r[top].x=i;
                r[top].y=j;
                r[top].w=Map[i][j];
                top++;
            }
        }
    }
    sort(r,r+top,cmp);
    int m=k,min=0;
    top=0;
    while(m<n-1)
    {
        if(!vis[r[top].x]&&vis[r[top].y])
        {
            m++;
            vis[r[top].x]=true;
            nodeset[r[top].x]=nodeset[r[top].y];
            min+=r[top].w;
        }
        else if(vis[r[top].x]&&!vis[r[top].y])
        {
            m++;
            vis[r[top].y]=true;
            nodeset[r[top].y]=nodeset[r[top].x];
            min+=r[top].w;
        }
        if(!vis[r[top].x]&&!vis[r[top].y])
        {
            m++;
            vis[r[top].x]=true;
            vis[r[top].y]=true;
            nodeset[r[top].x]=nodeset[r[top].y];
            min+=r[top].w;
        }
        else
        {
            if(nodeset[r[top].x]!=nodeset[r[top].y])
            {
                m++;
                int tmp=nodeset[r[top].x];
                for(int z=0;z<=n;z++)
                if(tmp==nodeset[z])
                nodeset[z]=nodeset[r[top].y];
                min+=r[top].w;
            }
        }
        top++;
    }
    return min;
}
void Init(int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    Map[i][j]=MAX;
    for(int i=0;i<=n;i++)
    nodeset[i]=i;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        Init(n);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        scanf("%d",&Map[i][j]);
        int k,BIT=0;
        scanf("%d",&k);//修建的路可能重复修建.
        for(int i=1;i<=k;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(!vis[a]&&vis[b])
            {
                BIT++;
                vis[a]=true;
                nodeset[a]=nodeset[b];
            }
            else if(vis[a]&&!vis[b])
            {
                BIT++;
                vis[b]=true;
                nodeset[b]=nodeset[a];
            }
            else if(!vis[a]&&!vis[b])
            {
                BIT++;
                vis[a]=true;
                vis[b]=true;
                nodeset[a]=nodeset[b];
            }
            else
            {
                if(nodeset[a]!=nodeset[b])
                {
                    BIT++;
                    int tmp=nodeset[a];
                    for(int x=0;x<=n;x++)
                    if(nodeset[x]==tmp)
                    nodeset[x]=nodeset[b];
                }
            }
            Map[a][b]=MAX;
            Map[b][a]=MAX;
        }
        printf("%d\n",Kruscal(n,BIT));
    }
}

Kruscal 写的太挫了，需要努力精简代码啊。