Light OJ 1011

题目大意：

有N个男人，和N个女人要互相匹配，每个男人和每个女人有个匹配值。 并且匹配只能是1对1的。 问所有人都匹配完成，最大的匹配值是多少？

 

状压DP，暴力枚举就OK了， 这个题目略坑，因为他卡常数，可以有一些简单的优化，能优化1500ms.............

=================================================================

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef unsigned long long LL;
const int INF = 1e9+7;
const int maxn = 105;
const int MOD = 9973;
int dp[20][70000];
int Men[20][20];
int main()
{
    int T, n, cas = 1;
    scanf("%d", &T);

    while(T --)
    {
        scanf("%d", &n);
        //   memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d", &Men[i][j]);

        int Lim =  (1<<n) - 1;
        for(int i=1; i<=n; i++)///前n个元素
        for(int j=0; j<=Lim; j++)
        {
            dp[i][j] = 0;
            int cnt = 0;
            for(int k=0; k<n; k++)
                if( j&(1<<k) ) cnt ++;

            if(cnt != i) continue;
            for(int k=1; k<=n; k++)
            {
                if( ((1<<(k-1))&j) )

                    dp[i][j] = max(dp[i][j], dp[i-1][j-(1<<(k-1))] + Men[i][k]);
            }
        }
        printf("Case %d: %d
", cas ++, dp[n][Lim]);
    }
    return 0;
}