题解：P10937 車的放置

tjtdrxxz · 2024-09-15 09:45:48 · 题解

前置知识：二分图

二分图是长这样滴： 一眼就能看出二分图类似于男女关系，A 喜欢 B，但 B 不一定喜欢 A，但 B 喜欢的人不一定喜欢 B。所以我们需要委屈下男方。如果有一对匹配好的男女（A 和 B），但又有另一个人（C）喜欢女方，我们就先把 C 和 B 连成一对，然后就看 A 能不能和别的女生匹配，类似这样：

本题思路

我们可以把每行每列都看成一个点，一辆车占据每行每列就相当于占据他所在的行和列代表的点。

那么为了找到最多的车，自然就是二分图最大匹配了。

这题的数据范围比较小， N, M \le 200 ，所以 O (n^2) 可以过。

code:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register char in = getchar(),f = 0; register int t = 0;
    for(;in < '0' || in > '9';in = getchar())if(!(in ^ 45))f = 1;
    for(;in >= '0' && in <= '9';in = getchar())
     t = (t << 1) + (t << 3) + (in ^ 48);
    return f ? -t : t;
}
void write(register long long x)
{
    static int t[25];register int tp = 0;
    if(x == 0)return(void)(putchar('0'));
    else if(x < 0) putchar('-'),x = -x;
    while(x) t[tp++] = x % 10,x /= 10;
    while(tp--) putchar(t[tp] + 48);
}
#define stdi stdin
#define stdo stdout
int n = read(),m = read(),t = read();
int vis[1012][1012],ans,dis[100012];
int lk[100012];
inline short dfs(int u)
{
    for(int i = 1;i <= m;i++)
    {
        if(!vis[u][i] && !dis[i])
        {
            dis[i] = 1;
            if(!lk[i] || dfs(lk[i]))
            {
                lk[i] = u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    setvbuf(stdi,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
    setvbuf(stdo,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
    for(int i = 1;i <= t;i++)
    {
        register int u = read();
        register int v = read();
        vis[u][v] = 1;
    }
    for(int i = 1;i <= n;i++)
    {
        memset(dis,0,sizeof(dis));
        if(dfs(i)) ans++;
    }
    write(ans),puts("");
}