在此处输入标题

未分类

在此输入正文

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500*500+10;
struct edge
{
    int from,to;
    int cost;
}mxr[maxn];
int par[maxn];
int n;
int cmp(edge a,edge b)
{
    return a.cost<b.cost;
}
void init(){
    for(int i=1;i<=n;i++)
        par[i]=i;
}
int find(int x)
{
    if(par[x]==x)
        return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
        par[x]=y;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int kruskal()
{
    int res=0;
    int k=n*(n-1)/2;
    sort(mxr+1,mxr+k+1,cmp);
    for(int i=1;i<=k;i++)
    {
        if(same(mxr[i].from,mxr[i].to))
            continue;
        unite(mxr[i].from,mxr[i].to);
        res+=mxr[i].cost;
    }
    return res;
}
int main()
{
    int flag;
    while(scanf("%d",&n),n)
    {
        init();
        for(int i=1;i<=n*(n-1)/2;i++)
        {
            for(int j=1;j<=4;j++)
            {
                scanf("%d %d",&mxr[i].from,&mxr[i].to);
                scanf("%d %d",&mxr[i].cost,&flag);
                if(flag) unite(mxr[i].from,mxr[i].to);
            }
        }
        printf("%d\n",kruskal());
    }
    return 0;
}