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

简单匈牙利 为啥时匈牙利呢？ 因为本小可爱的$dicnic$写挂了$qwq$ 对于对角线上的每个点判断一下 然后注意一下全是$1$的情况 上代码 ```cpp // 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 */ ```