题解：P10937 車的放置

原题链接

• 洛谷 P10937 車的放置

解题思路

其实就是匈牙利板子

题意翻译一下就是每一行每一列都只能选一个点。

所以我们就可以建一张二分图，将行和列转化为点存储。

对于每一个可选的点，在行和列对应的点之间连一条边。

因为每行只能对应一列，所以能放的最大个数就是二分图的最大匹配。

参考代码

#include <bits/stdc++.h>
#define N 205
#define M 205
using namespace std;

int n , m , t , p[M] , ans = 0;
bool able[N][M] , vis[M];
vector <int> g[N];

bool match(int x)
{
    for(int i = 1 ; i <= m ; i++)
    {
        if(able[x][i] && !vis[i])
        {
            vis[i] = 1;
            if(!p[i] || match(p[i]))
            {
                p[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(able , true , sizeof able);
    cin >> n >> m >> t;
    for(int i = 1 , x , y ; i <= t ; i++)
    {
        cin >> x >> y;
        able[x][y] = 0;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        memset(vis , 0 , sizeof(vis));
        if(match(i))
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}