洛谷 P2016 战略游戏

战略游戏

这题洛谷上有很多树形dp的题解，在这里我提供另外一种做法，那就是最小点覆盖的做法。

最小点覆盖

有关最小点覆盖的概念请自行csdn，知道了概念以后再把题目抽象一下，会发现这题就是一道最小点覆盖的板子题。此外还要知道一个结论，那就是最小点覆盖的点数等于最大边匹配的边数，对于无向图来说，就等于最大边匹配的边数的一半。知道这个以后，那么这个题就变成了匈牙利算法求二分图最大边匹配了，直接上代码。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define N 1505
int belong[N], vis[N];
vector <int> edge[N];
bool find(int u)
{
    for(int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(belong[v] == -1 || find(belong[v]))
            {
                belong[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(belong, -1, sizeof(belong));
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int u, num;
        cin >> u >> num;
        while(num--)
        {
            int v;
            cin >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(find(i))
            ans++;
    }
    cout << ans / 2 << endl;
    return 0;
}

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
51
52