题解 P1129 【[ZJOI2007]矩阵游戏】

简单匈牙利

为啥时匈牙利呢?

因为本小可爱的 $dicnic$ 写挂了 $qwq$

对于对角线上的每个点判断一下

然后注意一下全是 $1$ 的情况

上代码

// luogu-judger-enable-o2
/*
    by Qingnian Su
    2018.7.26
    9:28
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t;
int n;
int map[210][210];
int dfn[210];
int alist[210];
bool ins[210];bool opt;
bool dfs(int x)
{
//  printf("%d\n",x);
    for(int i=1;i<=alist[x];i++)
      if(!ins[map[x][i]]){
//      printf("%d %d %d\n",x,i,map[x][i]);
        ins[map[x][i]]=true;
//      printf("%d %d\n",dfn[ins[map[x][i]]],dfs(dfn[map[x][i]]));
        if(!dfn[map[x][i]]||dfs(dfn[map[x][i]])){
          dfn[map[x][i]]=x;return true;}
      }
//    printf("qwq %d\n",x);
    return false;
}
void clear()
{
    memset(map,0,sizeof(map));
    memset(dfn,0,sizeof(dfn));
    memset(alist,0,sizeof(alist));
//  memset(ins,0,sizeof(ins));
    return ;
}
int main()
{
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
            scanf("%d",&opt),
            opt=opt==1?map[i][++alist[i]]=j:false;
        for(int i=1;i<=n;i++){
            memset(ins,0,sizeof(ins));
            if(!dfs(i)){puts("No");goto rp;}
        }
        puts("Yes");rp:;
    }
}
/*
1
2
1 1 
1 1 
*/

发表于 2018-07-26 09:59:04 in 题解