NC236758 占领城市 (最小路径点覆盖)

题目描述
Intercept在玩一种游戏，游戏中有 n 座城市，城市之间用单向的道路连接，形式化地说，n 座城市构成了一个有向无环图。Intercept可以控制一些毁灭机器人，对于每一个毁灭机器人，Intercept可以让它从任意一座城市出发，沿着道路以任意的路径移动，在任意一座城市停止。毁灭机器人每经过一座城市，这座城市都会被占领。但是，任意两个毁灭机器人不能经过同一座城市，因为毁灭机器人也会消灭毁灭机器人。Intercept想知道，他至少需要准备多少毁灭机器人，才能占领所有城市。
注意：因为Intercept可以在所有点都设置一个毁灭机器人，所以一定是有解的。
题目链接：
https://ac.nowcoder.com/acm/problem/236758
思路：
拆点思想，将每个点拆成入点和出点。
初始时，假设每个未拆的点都放置一个机器人，那么拆点后，每一次匹配就意味着这两个城市可以共用一个机器人。那么机器人数量就可以相较于之前 -1。
那么我们希望公用的机器人越多越好，也就是最大匹配。
最后的结果就是n-最大匹配。
类似题目：
Acwing 379. 捉迷藏
是最小路径重复点覆盖问题
题解：https://blog.csdn.net/weixin_50616227/article/details/125787640?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165934079416781647596413%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=165934079416781647596413&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_ecpm_v1~rank_v31_ecpm-1-125787640-null-null.nonecase&utm_term=%E6%8D%89%E8%BF%B7%E8%97%8F&spm=1018.2226.3001.4450
代码：

#include
#include
#include
using namespace std;
bitset<510>g[510];
bool st[510];
int n,m;
int match[510];
bool find(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(!g[u][i])
        {
            continue;
        }
        if(st[i])
        {
            continue;
        }
        st[i]=true;
        if(match[i] == -1 || find(match[i]))
        {
            match[i]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    memset(match,-1,sizeof match);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>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++;
        }
    }
    cout<<n-res<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50