hdu 3225 Flowers Placement （dfs+匈牙利算法剪枝，太神了）
题意：给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行，并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案，那么输出-1.
思路：有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE…
想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。
比较重要的一点是。。。
n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。
我们可以根据这个来剪枝。
具体做法：
**我们先求出一个完备匹配，然后搜索每个位置能够种的花，假设当前位k置种了花i,那么判断k+1--n位置能不能形成一个完备匹配（即能否种出满足条件的花），若能那么当前位置可以种该花，继续搜索，若不能这返回**
然后把一个false写了true.调了一个小时。。。。。。。。。。。。。。无语凝噎。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月27日 星期五 00时42分16秒
4File Name :code/hdu/3225.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=305;
34bool lie[N][N];
35bool hang[N];
36int n,m,k;
37int cnt;
38//vector <int>ans[N]; //不用每个都存，只存第k个就好。。。前面的随便覆盖。。。
39int cur[N];
40int link[N],tmp[N];
41bool vis[N];
42bool g[N][N];
43
44
45bool findgirl( int x,int limit)
46{
47 if (x<=limit) return false;//找到的匹配位置一定要在当前的后面。
48 for ( int i = 1 ; i <= n ; i++)
49 {
50 if (g[x][i]&&!vis[i])
51 {
52 vis[i] = true;
53 if (link[i]==-1||findgirl(link[i],limit))
54 {
55 link[i] = x;
56 return true;
57 }
58 }
59 }
60 return false;
61}
62bool hungary()
63{
64 ms(link,-1);
65
66 for ( int i = 1 ; i <= n ; i++)
67 {
68 ms(vis,false);
69 if (!findgirl(i,0)) return false; //最大匹配的话。。。必须每个都匹配。。。
70 }
71 return true;
72}
73bool check ( int pos,int id) //pos表示位置，id表示数字，也就是花的种类。
74{
75 if (link[id]==pos) return true;
76 int kind;
77 for ( int i = 1 ; i <= n ; i++)
78 {
79 tmp[i] = link[i] ; //tmp[i]数组为了保护link.
80 if (link[i]==pos) kind = i ;//kind记录了之前做二分图最大匹配的时候当前位置放的花的种类是哪个。
81 }
82 int t = link[id];//t表示id种花在做二分图最大匹配之后的位置。
83 link[id] = pos;
84 link[kind] = -1; //把id种花放在了pos位置，那么原来在pos位置的花就要重新匹配，所以是未匹配。
85
86 ms(vis,false);
87 if (findgirl(t,pos)) return true;
88 else for ( int i = 1 ; i <= n ; i++) link[i] = tmp[i];
89 return false;
90
91
92}
93bool dfs( int j) //j 表示第几列。
94{
95 if (j==n+1)
96 {
97 cnt++;
98 if (cnt==k) return true; //只问了前k个。。所以搜到第k个就好。。。
99 return false;
100 }
101
102 for ( int i = 1 ; i <= n ; i++)
103 {
104 if (hang[i]) continue ; //表示这一行已经出现了数字i.
105 if (g[j][i]&&check(j,i))
106 {
107 // cout<<"j:"<<j<<" i:"<<i<<endl;
108 hang[i] = true;
109 cur[j] = i ;
110 if (dfs(j+1)) return true;
111 hang[i] = false; //回溯。
112 }
113 }
114
115 return false;
116}
117int main()
118{
119 #ifndef ONLINE_JUDGE
120 freopen("code/in.txt","r",stdin);
121 #endif
122 int T;
123 scanf("%d",&T);
124 int cas = 0 ;
125 while (T--)
126 {
127 ms(lie,false);
128 ms(hang,false);
129 ms(g,false);
130 ms(cur,0);
131 scanf("%d%d%d",&n,&m,&k);
132// cout<<"n:"<<n<<" m:"<<m<<" k:"<<k<<endl;
133 for ( int i = 1 ; i <= m ; i++)
134 for ( int j = 1 ; j <= n ;j++)
135 {
136 int x;
137 scanf("%d",&x);
138 lie[j][x] = true;
139// cout<<"j:"<<j<<" x:"<<x<<endl;
140
141 }
142
143 for ( int i = 1 ; i <= n ; i++) //n种花为左集合，n个位置为右集合。
144 for ( int j = 1 ; j <= n ; j++)
145 if (!lie[i][j]) g[i][j] = true;
146
147 if (!hungary()) //必须是完全匹配。。。。
148 {
149
150 printf("Case #%d: -1\n",++cas);
151 continue;
152 }
153
154 cnt = 0;
155// cout<<"cnt:"<<cnt<<endl;
156 if (!dfs(1))
157 {
158 printf("Case #%d: -1\n",++cas);
159 }
160 else
161 {
162 printf("Case #%d: ",++cas);
163
164 for ( int i = 1 ; i <= n-1 ; i++)
165 printf("%d ",cur[i]);
166 printf("%d\n",cur[n]);
167 }
168 }
169
170 #ifndef ONLINE_JUDGE
171 fclose(stdin);
172 #endif
173 return 0;
174}