题目链接
大概题意是有n个男的n个女的（原谅我这么说，我是粗人），给你一个n*n的矩阵，第i行第j列表示第i个女（男）对第j个男（女）的好感度，然后要安排n对相亲，保证都是正常的（无搞基百合之类的），然后求怎么安排能使好感度和最大，求出最大值。
开始试了纯暴力的方法，时间复杂度是n！果断超时
代码语言：javascript复制#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int vis[17];
int n, ans, sum;
int map[19][19];
void dfs(int x)
{
if (x == n 1)
{
ans = max(ans, sum);
return;
}
for (int i = 1; i <= n; i )
{
if (vis[i] == 0)
{
sum = map[x][i];
vis[i] = 1;
dfs(x 1);
vis[i] = 0;
sum -= map[x][i];
}
}
}
int main()
{
int t;
cin >> t;
for (int kase = 1; kase <= t; kase )
{
cin >> n;
for (int i = 1; i <= n; i )
for (int j = 1; j <= n; j )
cin >> map[i][j];
sum = 0;
ans = 0;
memset(vis, 0, sizeof(vis));
dfs(1);
cout << "Case " << kase << ": " << ans << endl;
}
return 0;
}后来因为一个小小的弱智的错误 wa了5 6次。代码中用了很多位运算，通过位运算很方便的把状态进行了压缩存储起来。
代码语言：javascript复制//2013-06-25-22.05
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn = 1<<16;
int vis[17];
int n, ans, sum;
int map[19][19];
int dp[maxn];
int dfs(int x, int d)
{
if (x == 0)
return 0;
if (dp[x])
return dp[x];
for (int i = 0; i < n; i )
{
if (x&(1<<i))
dp[x] = max(dfs(x^(1<<i), d-1) map[i 1][d], dp[x]);
}
return dp[x];
}
int main()
{
int t;
cin >> t;
for (int kase = 1; kase <= t; kase )
{
cin >> n;
for (int i = 1; i <= n; i )
for (int j = 1; j <= n; j )
cin >> map[i][j];
memset(dp, 0, sizeof(dp));
ans = dfs((1<<n)-1, n);
printf("Case %d: %dn", kase, ans);
}
return 0;
}
