洛谷P1129 [ZJOI2007] 矩阵游戏 题解

题目链接：P1129 [ZJOI2007] 矩阵游戏

题意：给定一张有黑白棋子的正方形棋盘，问存不存在解法使得经过若干次交换行或列的操作后，左上角至右下角的对角线上所有的点放着黑色棋子

说实话第一眼看到这个题我连暴力都不知道咋打

这道题的建模挺有意思的

对于 \(\forall i \in \mathbb{Z}, 1\le i \le n\) ，要求第 \(i\) 行第 \(i\) 列为黑色

不妨可以看作行结点 \(i\) 与列结点 \(i\) 之间有一条无向边（显然没有权重）

则交换行 \(u,v\) 的操作，就可以看作重命名的操作

问题就可以转化为行结点集 \(V_a\) 与列结点集 \(V_b\) 求二分图最大匹配

当最大匹配值为 \(n\) 时，存在解

时间复杂度 \(O(Qn^2)\) ，\(Q\) 为数据的组数

代码如下（忽略那个快读，其实没有什么大用处 qwq）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
// ---------------------------------------------------- qwq
#define N (int)(205)
int n,Q,vis[N],mch[N],d[N][N];
int dfs(int u,int now)
{
    if(vis[u]==now)
        return 0;
    vis[u]=now;
    for(int i=1; i<=n; i++)
        if(d[u][i]&&(!mch[i]||dfs(mch[i],now)))
            {mch[i]=u;return 1;}
    return 0;
}
int hgn()
{
    memset(vis,0,sizeof(vis));
    memset(mch,0,sizeof(mch));
    int ans=0;
    for(int i=1; i<=n; i++)
        ans+=dfs(i,i);
    return ans;
}
signed main()
{
    read(Q);
    while(Q--)
    {
        read(n);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                read(d[i][j]);
        puts((hgn()==n)?"Yes":"No");
    }
    return 0;
}