[luoguP1129] [ZJOI2007]矩阵游戏（二分图最大匹配）

传送门

每一行的1和每一列的1不管怎么换还是在同一行和同一列

目标状态中有n个1是不同行且不同列的

那么就是能否找出n个不同行不同列的1

就是每一行选一个不同列的1

如果矩阵中位置i，j为1，那么点i到点j连一条边

跑匈牙利即可

#include <cstdio>#include <cstring>#include <iostream>#define N 201using namespace std;int T, n, cnt;int head[N], to[N * N], nex[N * N], belong[N];bool vis[N];inline int read()inline bool dfs(int u)}}return 0;}inline bool solve()return ans == n;}inline void add(int x, int y)int main()if(solve()) puts("Yes");else puts("No");}return 0;}

上一篇：[luoguP3960] 列队（动态开点线段树）

下一篇：[luoguP2495] [SDOI2011]消耗战（DP + 虚树）