学步园

题目链接：怒点

开始学习最小生成树的Kruscal算法了，还行，和prim是有区别的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Max=5000;
struct X
{
    int x,y;
    int q;
}l[Max];
bool cmp(X x,X y)
{
    if(x.q<y.q) return true;
    return false;
}
int Kruscal(int n,bool vis[],int Yet,int nodeset[],int t)
{
    int m=Yet,first=0,min=0;
    sort(l,l+t,cmp);
    while(m<(n-1))
    {
        if(!vis[l[first].x]&&vis[l[first].y])
        {
            min+=l[first].q;
            vis[l[first].x]=true;
            nodeset[l[first].x]=nodeset[l[first].y];
            m++;
        }
        else if(vis[l[first].x]&&!vis[l[first].y])
        {
            min+=l[first].q;
            vis[l[first].y]=true;
            nodeset[l[first].y]=nodeset[l[first].x];
            m++;
        }
        else if(!vis[l[first].x]&&!vis[l[first].y])
        {
            min+=l[first].q;
            vis[l[first].y]=true;
            vis[l[first].x]=true;
            nodeset[l[first].y]=nodeset[l[first].x];
            m++;
        }
        else
        {
            if(nodeset[l[first].x]!=nodeset[l[first].y])
            {
                min+=l[first].q;
                int temp=nodeset[l[first].x];
                for(int j=1;j<=n;j++)
                if(temp==nodeset[j])
                nodeset[j]=nodeset[l[first].y];
                m++;
            }
        }
        first++;
    }
    return min;
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        bool vis[105];
        memset(vis,false,sizeof(vis));
        int a,b,c,mark,Yet=0,nodeset[105],first=0;
        for(int i=0;i<=n;i++)
        nodeset[i]=i;
        for(int i=1;i<=n*(n-1)/2;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&mark);
            if(!mark)
            {
                l[first].x=a;
                l[first].y=b;
                l[first].q=c;
                first++;
            }
            else
            {
                if(!vis[a]&&vis[b])
                {
                    nodeset[a]=nodeset[b];
                    vis[a]=true;
                }
                else if(vis[a]&&!vis[b])
                {
                    nodeset[b]=nodeset[a];
                    vis[b]=true;
                }
                else if(!vis[a]&&!vis[b])
                {
                    nodeset[a]=nodeset[b];
                    vis[a]=true;
                    vis[b]=true;
                }
                else
                {
                    if(nodeset[a]!=nodeset[b])
                    {
                        int temp=nodeset[a];
                        for(int k=1;k<=n;k++)
                        if(temp==nodeset[k])
                        nodeset[k]=nodeset[b];
                    }
                }
                Yet++;
            }
        }
        printf("%d\n",Kruscal(n,vis,Yet,nodeset,first));
    }
    return 0;
}

冗余太多，以后要一步步的精简。

做出来这道题，让我刷了一版，重要的在已经连通的路上出现了一点问题。