Light OJ 1029 Civil and Evil Engineer

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    for(int i=0;i<n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    //ofstream o("op.txt");
    int i,j,k,l,n,m,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        for(i=1;;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            if(u==0&&v==0&&w==0)
                break;
            edge get;
            get.u=u;
            get.v=v;
            get.w=w;
            e.push_back(get);
        }
        int ans=0;
        sort(e.begin(),e.end());
        ans+=mst(n+1);
        reverse(e.begin(),e.end());
        ans+=mst(n+1);
        cout<<"Case "<<k<<": ";
        if(ans%2==0)
            cout<<ans/2<<endl;
        else
            cout<<ans<<"/"<<2<<endl;
        e.clear();
    }
    return 0;
}