lightoj1029

CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct e
{
        int u,v,w;
}edge[200005];
int fa[200005];
int n,m,ncase;
bool cmp1(e s1,e s2)
{
        return s1.w<s2.w;
}
bool cmp2(e s1,e s2)
{
        return s2.w<s1.w;
}
int find(int x)
{
        return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool judge()
{
        for(int i=0;i<=n;i++)
        {
                if(fa[i]==i)return false;
        }
        return true;
}
void kruskal()
{
        sort(edge,edge+m,cmp1);
        int res=0;
        for(int i=0;i<m;i++)
        {
                int ra=find(edge[i].u),rb=find(edge[i].v);
                if(ra!=rb)
                {
                        fa[ra]=rb;
                        res+=edge[i].w;
                }
        }
        sort(edge,edge+m,cmp2);
        int res1=0;
        for(int i=0;i<=n;i++)fa[i]=i;
        for(int i=0;i<m;i++)
        {
                int ra=find(edge[i].u),rb=find(edge[i].v);
                if(ra!=rb)
                {
                        fa[ra]=rb;
                        res1+=edge[i].w;
                }
        }

        if ((res + res1) % 2 == 0)
                printf("Case %d: %d\n", ++ncase, (res + res1) / 2);
        else
                printf("Case %d: %d/2\n", ++ncase, res + res1);
}
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                m=0;
                cin >>n;
                for(int i=0;i<=n;i++)fa[i]=i;
                while(1)
                {
                        scanf("%d%d%d",&edge[m].u,&edge[m].v,&edge[m].w);
                        if(edge[m].u==0&&edge[m].v==0&&edge[m].w==0)break;
                        m++;
                }
                m++;
                kruskal();
        }
        return 0;
}