题目描述

给定一个N行M列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能互相攻击的車。

車放在格子里，攻击范围为它所在的这一行与这一列。

样例

输入样例：

8 8 0

输出样例：

8

算法1

(二分图匈牙利算法)

每个車放置在一个格子时，该行与该列均不能在放車了。
每个車的放置都需要一个行标号与一个列标号来确定位置，而这与二分图匈牙利算法的唯一匹配性质相符
所以可以想到，将行标号当做二分图的左图，列标号当做二分图的右图，車则是匹配边，进行匈牙利。

C++ 代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            w=-w;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=s*10+c-'0';
        c=getchar();
    }
    return s*w;
}
const int N=205;
int n,m,k,ans;
int fri[N];
bool flag[N][N],vis[N];
bool dfs(int x)
{
    for(int y=1;y<=m;y++)
    {
        if(flag[x][y]||vis[y])
            continue;
        vis[y]=1;
        if(!fri[y]||dfs(fri[y]))
        {
            fri[y]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=k;i++)
    {
        int x,y;
        x=read();
        y=read();
        flag[x][y]=1;
    }
    ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}