lightoj1049

CODE

#include <iostream>
#include <cstring>
using namespace std;
int ans=0;
int ncase;
int n;
int g[105][105];
void dfs(int u,int fa)
{
        //cout << u<<endl;
        for(int i=1;i<=n;i++)
        {
                if(g[u][i]!=-1&&i!=fa)
                {
                        ans+=g[u][i];
                        g[u][i]=-1;
                        dfs(i,u);
                        return;
                }
        }
}
int main()
{
        int t;
        cin >>t;
        while(t--)
        {
                ans =0;
                cin >> n;
                int sum  =0;
                memset(g,-1,sizeof(g));
                for(int i=0;i<n;i++)
                {
                        int u,v,w;
                        cin >> u >> v>> w;
                        g[u][v]=0;
                        g[v][u]=w;
                        sum+=w;
                }
                dfs(1,-1);
                //cout << ans<<endl;
                cout << "Case "<<++ncase<<": "<<min(ans,sum-ans)<<endl;
        }
        return 0;
}