Bzoj 1059(二分图最大匹配)

Bzoj 1059
想算法的时候自己多搞几个数据找一找规律和结论,特别是这种看起来就会有规律和结论的题目,很重要!
通过搞几个数据,发现:在同行同列的两个$1$,它们对答案的贡献是相同的,因为无论怎么调换,这两个$1$都会在同行同列。又因为要对角线上都是$1$,所以问题转化为:找到$n$个点使得这$n$个点不在同行同列上。这样我们把$x$坐标弄到左边,$y$坐标弄到右边,如果$(i,j)=1$,在左边$i$连一条边到右边$j$,然后做一个二分图最大匹配,如果不能全部都匹配,就不能完成了

1
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200 + 5;
vector<int> G[MAXN];
int cnt, n, lk[MAXN], vis[MAXN];
bool hungary(int u) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (vis[v] != cnt) {
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
lk[v] = u;
return true;
}
}
}
return false;
}
void clean() {
for (int i = 0; i <= n; i++) lk[i] = vis[i] = 0, G[i].clear();
}
void solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; i++) {
for (int x, j = 1; j <= n; j++) {
scanf("%d", &x);
if (x == 1) G[i].push_back(j);
}
}
for (int i = 1; i <= n; i++) {
if (!hungary(cnt = i)) {
printf("No\n");
return ;
}
}
printf("Yes\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

------ 本文结束 ------