BUPT-2022-summer-3

发表于 | 分类于 |

B(图论+贪心dp)

给定一张节点数小于1e5的无环无向图，有以下规定:

  1. 你可以强制monitor任意节点
  2. 被强制monitor的节点，其相邻节点和对应的连边都会被monitor
  3. 若一条边被monitor，则其对应的节点也被monitor
  4. 若一个边的对应两个节点都被monitor，则该边也被monitor
  5. 若一个节点和k条边相连，若k-1条边都被monitor，则剩下一条边也被monitor

现要求所有的节点和边都被monitor，求最少需要强制monitor多少个节点

正解:复杂的规则+图，考虑用dfs+贪心转移解决

考虑当前节点和其所有子节点、父节点，假设未被monitor子节点数为k

若k>=2,则对当前节点强制monitor能monitor所有子节点和父节点，若不对当前节点强制monitor，则在当前节点不为强制monitor的情况下，想要monitor其子节点，必须强制monitor子节点本身(因为k>=2不能满足规则5使边被monitor)，由于k>=2，故此时强制monitor当前节点花费最小且成效最大(父节点也被monitor)

若k==1，则依据规则3、4可知，该子节点的其他边都未被monitor，该子节点和当前节点的连边也未被monitor，当前节点与其父节点的连边monitor后，则该子节点与当前节点的连边也被monitor，则该子节点和该节点的所有边都会被monitor，故我们延后处理(即不做任何处理)

若k==0，则所有子节点都被monitor，如果当前节点也被monitor，则当前节点与父节点的连边，根据规则5，也被monitor，再根据规则3，当前节点的父节点也一定会被monitor；如果当前节点没被monitor，则无事发生

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 100005;
ll tmp, T, n, m;
bool vis[maxn];
ll ans = 0;
vector<ll> g[maxn];
void dfs(ll x,ll fa)
{
    for(auto&e:g[x])
    {
        if(e!=fa)
        {
            dfs(e, x);
        }
    }
    ll cnt = 0;
    ll tmp;
    for(auto&e:g[x])
    {
        if(e!=fa)
        {
            if(!vis[e])
            {
                cnt++;
                tmp = e;
            }
        }
    }
    if(cnt>=2)
    {
        vis[x] = 1;
        vis[fa] = 1;
        ans++;
    }else if(cnt==0&&vis[x]==1)
    {
        vis[fa] = 1;
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cin >> T;
    while (T--)
    {
        cin >> n;
        ll x, y;
        
        for (ll i = 1; i < n;i++)
        {
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        memset(vis, 0, sizeof(vis));
        ans = 0;
        dfs(1, 0);
        if(!vis[1])
        {
            ans++;
            vis[1] = 1;
        }
        cout << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

在场上的时候没读懂规则3和规则4