象棋发表时间：2022-10-27 20:21 象棋 描述 你有足够多的象棋“车”，在一个 n×n 的棋盘上你能放多少个“车”呢？注意，所给棋盘上有些位置不能放任何东西。同时，某一行（列）最多只能存在一个“车”。 输入 第一行为一个正整数 n。 接下来 n 行，每行包含n 个整数，若为 0 表示这个位置不能放“车”；若为 1 表示这个位置可以放“车”。 输 输出一个整数，表示最多能放多少个“车”。 样例 1 输入 5 10000 00000 00010 11010 00010 样例 1 输 样例 1 解释 我们这样放就只能放 2 个“车”： 0000 0 0001 0 110车 0 0001 0 若我们这样放就能放下 3 个了： 样例 2 请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。 限制 对于 30%的数据，n ≤ 5； 对于 60%的数据，n ≤ 20； 对于 100%的数据，n ≤ 500。时间：2 sec 空间：256 MB 提示 [将横坐标和纵坐标看做是二分图的 X 集和 Y 集，会了吗？] 代码 #include<iostream> #include<memory.h> #pragma warning(disable:4996)
using namespace std;
/*该算法思想源于匈牙利算法，其流程可参考以下网址的解析： https://blog.csdn.net/dark_scope/article/details/8880547 男性对应棋盘中的行，女性对应棋盘中的列 */
int* used;//用于存储棋盘中某一列是否被使用int* pointc;//用于存储某一列中被哪一行所使用int** cb;//用于存储棋盘
bool find(int x,int n) { int i, j; for (int j = 0; j < n; ++j) { if (cb[x][j] == 1 && used[j] == 0)//如果棋盘中该行中某一列为1且此列在此行中未 被使用，则使用此列 { used[j] = 1; if (pointc[j] == -1 || find(pointc[j],n))//若此列未被其他行所使用或者虽然 被其他行所使用，但是其他行能找到另外的解(匹配列数)，则其他行使用其他的解，该行使用该列 //此处的find(pointc[j],n)使用递归，从第pointc[j]行递归到第0行(假设第0行的某一列为1)，直到找到使得上面的所涉及的行数都 能找到另外的相匹配的列数 { pointc[j] = x; return true; } } } return false; }
int main() { int n; scanf("%d", &n); cb = new int*[n];//用于存储棋盘 used = new int[n]; pointc = new int[n];//用于存储某一列中被哪一行所使用 for (int i = 0; i < n; ++i) { cb[i] = new int[n]; pointc[i] = -1; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &cb[i][j]); } } int all = 0; for (int i = 0; i < n; i++) { memset(used, 0, sizeof(int)*n); //这个在每一步中清空 if (find(i, n)) all++; } cout << all << endl; return 0; } |