山西焦煤集团公司网站,wordpress 使用插件下载,前端学校网站开发视频教程,广告制作材料价格单虽然是一道水难题#xff0c;但是我这种蒟蒻还是要讲一讲的。 Description 小Q是一个非常聪明的孩子#xff0c;除了国际象棋#xff0c;他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行#xff08;如同国际象棋一般#xff0c;只是颜色是随意的…虽然是一道水难题但是我这种蒟蒻还是要讲一讲的。 Description 小Q是一个非常聪明的孩子除了国际象棋他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行如同国际象棋一般只是颜色是随意的。每次可以对该矩阵进行两种操作行交换操作选择 矩阵的任意两行交换这两行即交换对应格子的颜色列交换操作选择矩阵的任意行列交换这两列即交换 对应格子的颜色游戏的目标即通过若干次操作使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑 色。对于某些关卡小Q百思不得其解以致他开始怀疑这些关卡是不是根本就是无解的于是小Q决定写一个程 序来判断这些关卡是否有解。 Input 第一行包含一个整数T表示数据的组数。接下来包含T组数据每组数据第一行为一个整数N表示方阵的大 小接下来N行为一个N*N的01矩阵0表示白色1表示黑色。 Output 输出文件应包含T行。对于每一组数据如果该关卡有解输出一行Yes否则输出一行No。 Sample Input 2 2 0 0 0 1 3 0 0 1 0 1 0 1 0 0 Sample Output No Yes 【数据规模】 对于100%的数据N ≤ 200 题解显然模拟可知在同一行或同一列的格子无论如何移动都会保持在同一行列所以可以直接以行和列建图如果ai,j1就由i向j连一条边。 显然这是一个二分图直接套匈牙利即可。 代码 #includecstdio
#includecstring
#define r register
bool a[205][205],vis[405];
int linked[405];
int n,T;
bool match(int u){ for(r int i1;in;i){if(!a[u][i]||vis[i])continue;vis[i]1;if(linked[i]0||match(linked[i])){linked[i]u;return 1;}}return 0;
}
int main(){scanf(%d,T);while(T--){scanf(%d,n);for(r int i1;in;i)for(r int j1;jn;j)scanf(%d,a[i][j]);memset(linked,-1,sizeof linked);r int ans0;for(r int i1;in;i){memset(vis,0,sizeof(vis));ansmatch(i);}puts(ansn?Yes:No);}return 0;
} View Code 懒得写邻接表了~ 转载于:https://www.cnblogs.com/Marser/p/7364573.html
