AcWing 373. 車的放置(二分图的最大匹配数)
原题链接
简单
作者:
小小_88
,
2022-04-26 15:52:55
,
所有人可见
,
阅读 510
車的放置
C++ 代码
/*
本题要求每行、每列只能放1个车,某个格子 (i, j) 放了车,等于是占了第 i 行与第 j 行放车的名额。
因此我们可以把所有行、列看作节点,一共 n + m 个节点,如果格子 (i, j) 没有被禁止,就在第 i 行
对应的节点与第 j 列对应的节点之间连无向边
对于行之间,每个车不可能同时放在两个行上,所以任意两行之间不可能有边,列同理。
要在互不冲突的前提下放置最多的车,就是求上述二分图的最大匹配数。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
int n, m, t;
bool g[N][N]; //g[i][j] 表示 第i行对应的节点和第j列对应的节点之间是否有边。false 表示有边,true 表示无边
bool st[N]; //st[i] 表示第i行是否已经完成匹配
int match[N]; //match[i] 表示第i行的匹配对象 -> 第match[i]列
bool find(int u) //为第u行寻找匹配对象
{
for(int i = 1; i <= m; i++) //枚举能和第u行匹配的列
{
if(g[u][i] || st[i]) continue; //禁止或已经匹配,跳过
st[i] = true; //否则说明当前行有希望匹配,先标记
if(!match[i] || find(match[i])) //如果当前行没有匹配对象或匹配对象还有别的选择
{
match[i] = u; //匹配成功
return true;
}
}
return false; //匹配失败
}
int main()
{
scanf("%d%d%d", &n, &m, &t);
while(t--)
{
int x, y;
scanf("%d%d", &x, &y);
g[x][y] = true; //禁止
}
int res = 0; //记录最大匹配数
for(int i = 1; i <= n; i++) //为左半图(行)找匹配对象
{
memset(st, 0, sizeof st); //重置标记
if(find(i)) res++; //匹配成功,匹配数+1
}
printf("%d\n", res);
return 0;
}
悟了!悟了!悟了!!
# Orz