题目链接 https://www.luogu.org/problemnew/show/P1129
看到题目肯定首先会想到搜索.
然鹅数据范围 \(n<=200\) 这么大 (其实也不算太大), 肯定是不行的.
如果 \((i,j)\) 是 \(1\), 从 \(i\) 向 \(j\) 连一条边, 表示第 \(j\) 列可以交换第 \(i\) 列得到, 然后跑一遍匈牙利就行了 (Dinic 我不会啊).
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
- #define Close fclose(stdin);fclose(stdout);
- using namespace std;
- int s; char ch;
- inline int read(){
- s = 0; ch = getchar();
- while(ch <'0' || ch> '9') ch = getchar();
- while(ch>= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
- return s;
- }
- const int MAXN = 1010;
- const int MAXM = MAXN * MAXN;
- int match[MAXN], vis[MAXN];
- int n, T, a, Time, head[MAXN], num, ans;
- struct Edge{
- int next, to;
- }e[MAXM << 1];
- inline void Add(int from, int to){
- e[++num].to = to; e[num].next = head[from]; head[from] = num;
- }
- int find(int u){
- for(int i = head[u]; i; i = e[i].next)
- if(vis[e[i].to] != Time){
- vis[e[i].to] = Time;
- if(!match[e[i].to] || find(match[e[i].to])){
- match[e[i].to] = u;
- return 1;
- }
- }
- return 0;
- }
- int main(){
- T = read();
- while(T--){
- memset(head, 0, sizeof head);
- memset(match, 0, sizeof match);
- num = 0; n = read(); ans = 0;
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= n; ++j)
- if(read())
- Add(i, j);
- for(int i = 1; i <= n; ++i)
- ++Time, ans += find(i);
- if(ans == n) printf("Yes\n");
- else printf("No\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2806224.html