lightoj1011

CODE

#include <iostream>
#include <cstring>
using namespace std;
int m[20][20];
int dp[1<<16];
int nCase,n;
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                memset(dp,0,sizeof(dp));
                cin >> n;
                for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                                cin >> m[i][j];
                for(int i=1;i<=n;i++)
                        for(int j=0;j<(1<<n);j++)
                        {
                                int cnt=0;
                                for(int k=0;k<n;k++)
                                        if(j&(1<<k))cnt++;
                                if(cnt!=i-1)continue;
                                for(int k=0;k<n;k++)
                                {
                                        if(j&(1<<k))continue;
                                        dp[j|(1<<k)]=max(dp[j|(1<<k)],dp[j]+m[i][k+1]);
                                }
                        }
                cout << "Case "<<++nCase<<": "<<dp[(1<<n)-1]<<endl;
        }
        return 0;
}