首页 > [ZJOI2007]矩阵游戏
开通博客写题解
头像 Bernard5
发表于 2020-12-03 23:33:12
题意 给定一个的01方阵，问是否能够通过行交换和列交换使得主对角线上都是1. 思路 主对角线上都是1，这一条件等价于：对于每一行，都有唯一的与之对应的列上是。 即可转化为匈牙利算法。 Solution #include <bits/stdc++.h> #define sc(x) scan 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 威风镰鼬
发表于 2021-08-25 20:48:56
思路 本来想着这是一道最大匹配的水题，没想到忘了变量初始化WA了。用匈牙利算法水过，题意大概是这个意思，假设我们有两个点集X和Y，那么输入就可以转化为二分图两边点的连线情况。交换行列式的过程，实际上是固定一个点集，另外一个点集内部在交换位置（讲得很抽象，画图试试？）然后就可以想到只要每个点都有与之匹 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 夜语声烦-
发表于 2022-08-01 01:04:34
[ZJOI2007]矩阵游戏 #include <iostream> #include <cstring> using namespace std; const int N = 210; int n; bool g[N][N], st[N]; int match[N]; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”