lightoj1040

CODE

#include <iostream>
#include <cstring>
using namespace std;
int g[55][55];
int vis[55];
int d[55];
int n,ncase;
const int inf=0x3f3f3f3f;
int main()
{
        int t;
        cin >>t;
        while(t--)
        {
                int sum=0;
                memset(vis,0,sizeof(vis));
                memset(g,0x3f,sizeof(g));
                memset(d,0x3f,sizeof(d));
                cin >> n;
                for(int i=0;i<n;i++)
                        for(int j=0;j<n;j++)
                {
                        int tp;
                        cin >>tp;
                        sum+=tp;
                        if(tp&&g[i][j]>tp&&i!=j)
                                g[i][j]=g[j][i]=tp;
                }
                d[0]=0;
                for(int i=0;i<n;i++)
                {
                        int mi=inf,index=-1;
                        for(int j=0;j<n;j++)if(!vis[j])
                        {
                                if(mi>d[j]){mi=d[j];index=j;}
                        }
                        if(index==-1)break;
                        vis[index]=1;
                        for(int j=0;j<n;j++)if(!vis[j])
                        {
                                d[j]=min(d[j],g[index][j]);
                        }
                }
                int ans=0,f=0;
                for(int i=0;i<n;i++)
                {
                        if(d[i]>=inf)
                        {
                                f=1;break;
                        }
                        else
                                ans+=d[i];
                }
                ans=sum-ans;
                if(f)ans=-1;
                cout << "Case "<<++ncase<<": "<<ans<<endl;
        }
        return 0;
}