题意：
给定n个人，分两天晚上去夜总会开派对，要求每天恰好有n/2个人去，且每人去的夜总会各不相同。
每个人对不同的晚上不同的夜总会有不同的满意度，求一个方案使得所有人的满意度之和最大。
夜总会数量=人的数量=n，2<=n<=20，且n是偶数。
0<=每一项满意度<=10^6。
时间限制2s，空间限制4MB。
题解：
在这题上卡了很久…
初看这题觉得是费用流…写完发现图建错了…
然后改成暴力枚举哪些人在第一天晚上去再跑费用流…
每个人只和对应晚上的夜总会连边，然后两天晚上的夜总会再连到一个辅助点，再连到汇…
就避免了跑出来的东西有两人在不同的晚上去同一个夜总会…
理所当然地超时了…
后来换成比较擅长这种图的zkw费用流…快了很多，但还是严重超时…
然后开始怀疑自己的做法…试图写DP…很快放弃了…
然后突然发现自己之前建图时傻掉了，枚举夜总会在哪个晚上有人就可以把图变成二分图…
于是改改改…改成KM…还是严重超时…大数据跑100s…
于是弃疗了…去膜拜Tourist的代码…结果发现就是KM…只不过是非递归的KM…
都是KM…差距就是这么大…
主要原因就是点是一个个加进二分图的，如果在最后跑KM，就完全没有用到子图的信息…
用非递归KM的话…一层层下去，冗余运算就减少了很多。
简单来说这题的做法就是：
枚举夜总会，一边向图中加点一边跑KM，然后就可以了…(CF评测机快，2s可过…
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstring>
#define mv(a,b) memcpy(a,b,(n<<2)+4)
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
const int N = , INF = 0x7f7f7f7f;
int n,n2,w1[N][N],w2[N][N],w[N][N],ans,tans,lx[N],ly[N],sl[N],lk[N],pat[N];
bool by[N];
void dfs(int nn,int d1,int d2)
{
if(nn>n){ if(ly[]>ans) ans = ly[]; return; }
int _lx[N],_ly[N],_lk[N],_a,i,cy,cx,ny;
for(int ch=;ch<;ch++)
{
if(d1==n2&&ch==) continue;
if(d2==n2&&ch==) continue;
mv(_lx,lx), mv(_ly,ly), mv(_lk,lk);
if(ch) mv(w[nn],w1[nn]); else mv(w[nn],w2[nn]);
memset(sl,0x7f,(n<<)+), memset(by,,n+);
cy = ; lk[] = nn;
while(lk[cy])
{
by[cy] = ; cx = lk[cy]; int tmp = INF;
for(i=;i<=n;i++)
if(!by[i])
{
int t = -lx[cx]-ly[i]-w[cx][i];
if(t<sl[i]) sl[i] = t, pat[i] = cy;
if(sl[i]<tmp) tmp = sl[i], ny = i;
}
for(i=;i<=n;i++)
{
if(by[i]) lx[lk[i]] += tmp, ly[i] -= tmp;
else sl[i] -= tmp;
}
cy = ny;
}
while(cy) lk[cy] = lk[pat[cy]], cy = pat[cy];
dfs(nn+,d1+(ch),d2+(ch^));
mv(lx,_lx), mv(ly,_ly), mv(lk,_lk);
}
}
int main()
{
int i,j;
n2 = (n = read())>>;
for(i=;i<=n;i++) for(j=;j<=n;j++) w1[i][j] = read();
for(i=;i<=n;i++) for(j=;j<=n;j++) w2[i][j] = read();
dfs(,,);
printf("%d\n",ans);
return ;
}