lightoj1041

CODE

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;

struct edge
{
       int u;
       int v;
       int w;
       bool operator<(edge a)const{return w<a.w;}
}e[55];
int fa[55],ncase;
int find(int a)
{
        if(fa[a]==a)return a;
        else return fa[a]=find(fa[a]);
}

int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                int m,sum=0;
                int cnt=0;
                map<string,int> mp;
                cin >> m;
                for(int i=0;i<m;i++)
                {
                        int w;
                        string s1,s2;
                        cin >> s1 >> s2>> w;
                        if(!mp[s1])mp[s1]=++cnt;
                        if(!mp[s2])mp[s2]=++cnt;
                        e[i].u=mp[s1];
                        e[i].v=mp[s2];
                        e[i].w=w;
                }
                sort(e,e+m);
                for(int i=0;i<=cnt;i++)
                        fa[i]=i;
                int num=0;
                for(int i=0;i<m;i++)
                {
                        int a=e[i].u;
                        int b=e[i].v;
                        int c=e[i].w;
                        int ra=find(a);int rb=find(b);
                        if(ra!=rb)
                        {
                                fa[ra]=rb;
                                sum+=c;
                                num++;
                        }
                }
                if(num==cnt-1)
                {
                        cout <<"Case "<<++ncase<<": "<<sum<<endl;
                }
                else    cout <<"Case "<<++ncase<<": "<<"Impossible"<<endl;
        }
        return 0;
}