AcWing 373. 車的放置/(匈牙利算法)
原题链接
简单
作者:
殇ベ_11
,
2021-06-08 10:33:31
,
所有人可见
,
阅读 758
题目描述
给定一个 N 行 M 列的棋盘,已知某些格子禁止放置。
问棋盘上最多能放多少个不能互相攻击的車。
車放在格子里,攻击范围与中国象棋的“車”一致。
输入格式
第一行包含三个整数 N,M,T,其中 T 表示禁止放置的格子的数量。
接下来 T 行每行包含两个整数 x 和 y,表示位于第 x 行第 y 列的格子禁止放置,行列数从 1 开始。
输出格式
输出一个整数,表示结果。
数据范围
1≤N,M≤200
样例
输入样例:
8 8 0
输出样例:
8
算法1
C++ 代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3;
const int M = 1e6;
int n,m,k;
int match[M];
int g[N << 1][N << 1];
bool st[M];
bool find(int u){
for(int i = 1;i <= m;i ++)
{
if(!st[i]&& !g[u][i]){
st[i] = true;
if(!match[i] || find(match[i])){
match[i] = u;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i <= k;i ++){
int x,y;
scanf("%d%d",&x,&y);
g[x][y] = true;
}
int res = 0;
for(int i = 1;i <= n;i ++){
memset(st,false,sizeof st);
if(find(i)) res++;
}
printf("%d",res);
return 0;
}