@[L541607090121](/user/325469) 用dinic试试
by __gcd @ 2020-04-06 11:11:11
邻接矩阵放在参数里面还是第一次见qwq
by __gcd @ 2020-04-06 11:12:50
@[一只大头](/user/149192) 我是想省去清空每组数据二分图的时间，就传递个领接表，但是感觉也不至于超时啊。。。刚学会二分图的匈牙利算法，不会那个。
by L541607090121 @ 2020-04-06 11:21:45
@[L541607090121](/user/325469) 我现在在外面没有电脑qwq我回家帮你看看
by __gcd @ 2020-04-06 11:24:50
@[一只大头](/user/149192) 非常感谢！我刚才把vector数组放在外面了，然后每次清空操作。过了。难道是因为创建数组比清空数组耗时嘛，这时间也相差太多了吧。
```cpp
#include <bits/stdc++.h>
using namespace std;
/*
考察二分图的最大匹配集
分析将题目抽象为二分图模版
经过行列变换使得主对角线格子为黑色，则有每一个行号分别匹配对应的列号
即行号和列号为顶点，初始地图中，mp[i][j]为黑色块，则表示i,j有边，将列号设置为 n+j
若能组成完美匹配集。则有解，否则无解
因为若每个行号都能找到不同的列号匹配，经过行列变换一定可以变换成
行号1对应列号1,行号2对应列号2.....
*/
const int maxn = 420;
int matching[maxn], n;
bool book[maxn];
vector<vector<int> > v(maxn + 2);
void init() {
for (int i = 1; i <= 2 * n; i++) {
matching[i] = -1;
}
for (int i = 1; i <= n; i++)
v[i].clear();
}
int dfs(int x) {
for (int i = 0; i < v[x].size(); i++) {
int u = v[x][i];
if (!book[u]) {
book[u] = true; // 只标记右边的点，因为每次遍历的都是左边的点，左边点和左边点没有边
if (matching[u] == -1 || dfs(matching[u])) { // 如果是未匹配点
matching[x] = u; // 将非匹配边变为匹配边
matching[u] = x;
return 1;
}
}
}
return 0;
}
int main(int argc, char** argv) {
int t, x;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
init();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &x);
if (x == 1) {
v[i].push_back(j + n);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (matching[i] == -1) {
memset(book, 0, sizeof(book)); // 每次找到未匹配点都要将标记数组置为False
book[i] = true;
ans += dfs(i); // 找到增广路
}
}
if (ans == n) // 完美匹配
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
```
by L541607090121 @ 2020-04-06 11:31:51
@[L541607090121](/user/325469) 震惊
by __gcd @ 2020-04-06 11:34:07
@[L541607090121](/user/325469) 所以还是老老实实清空吧
by __gcd @ 2020-04-06 11:34:52
现在只有POJ卡我的清空
by __gcd @ 2020-04-06 11:36:05
@[L541607090121](/user/325469)
我也是用匈牙利做的，我感觉会不会是你写挂了，我用邻接矩阵都没T啊。
by Rainy7 @ 2020-04-06 11:40:52
~~emmm等等问题解决了啊那没事了~~
by Rainy7 @ 2020-04-06 11:42:42