P1129矩阵游戏

· · 题解

这是一幅二分图，黑色的点代表行，蓝色的点代表列；

我们给每一行每一列一个id,初始状态下id[i]=i,例如初始状态下的第一列为1，以后不管它变为第几列，它的id就是1，图中的点表示的是行或列的id；

如果第i行第j列是1，就给id[i]和id[j]连一条边；

这是将第一列和第三列交换以后的情况，红色的是被改变的边，可以发现，这样的改变只是把两个节点的位置调换了一下，其实和原来的图是一样的，只是蓝色节点3和蓝色节点1位置不同而已，也就是说，这样的交换并不改变整体，不改变最大匹配。

于是，我们便可以按照原来的图找最大匹配ans，若ans=n，即yes,否则，即no；

图画的太丑请见谅

上代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxN=500;
int n,ans,t;
int matched[maxN+1];
bool G[maxN+1][maxN+1],vis[maxN+1];
bool dfs(int x)
{
    for(int i=1;i<=n;i++)
            if(G[x][i]&&!vis[i])
            {
                vis[i]=true;
                if(!matched[i]||dfs(matched[i]))
                {
                    matched[i]=x;
                    return true;
                }
            }
    return false;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(matched,0,sizeof(matched));
        memset(G,false,sizeof(G));
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++) scanf("%d",&G[i][j]);
        for(int i=1;i<=n;i++)
        {
            memset(vis,false,sizeof(vis));
            ans+=dfs(i);
        }
        if(ans==n) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}