Codeforces Round #408 (Div. 2) D. Police Stations 最短路、BFS

My Solution

题意：有一棵无根树，有一些节点上有一些标记(police station)，初始时满足，每个节点至少 与一个被标记过的节点相连且距离不超过d，要求去掉尽可能多的节点，使剩余的图依然满足，每个节点至少 与一个被标记过的节点相连且距离不超过d。

最短路、BFS

本来用dfs写了一发，后来发现很多情况下会重复去掉边。

用BFS来做比较好，从所有的被标记过的节点开始BFS，当接下来的边会导向已经访问过的节点时把这条边减去，否则放入队列。

这样每个节点都会与一个被标记过的节点直接或间接的相连，且距离不超过d。

最终会被减掉m-1条边，m表示size{unique{pi}}.

这里可以用反证法证明，如果减掉m-1+a(a>0)条边，则图会被切成大于等于m+1块，然后只有m个点被标记，所以必定有些块不满足要求。

反之，如果减点 m-1-a(a>0)，则图会边切成小于等于m-1块，这个时候根据鸽巢原理，至少存在一个块中有2个节点被标记，显然还有更优的方案。

复杂度 O(n)

1. #include   
2. #include   
3. #include   
4. #include   
5. #include   
6. #include   
7. using namespace std;  
8. typedef long long LL;  
9. typedef pair<int, int> ii;  
10. const int MAXN = 3e5 + 8;  
11.   
12. vector sons[MAXN];  
13. queue que;  
14. bool vis[MAXN], f[MAXN];  
15.   
16. inline void bfs()  
17. {  
18.     int fa, u, v, sz, i;  
19.     while(!que.empty()){  
20.         u = que.front().first;  
21.         fa = que.front().second;  
22.         que.pop();  
23.         if(vis[u]) continue;  
24.         vis[u] = true;  
25.         sz = sons[u].size();  
26.         for(i = 0; i < sz; i++){  
27.             v = sons[u][i].first;  
28.             if(v == fa) continue;  
29.             if(vis[v]){  
30.                 f[sons[u][i].second] = true;  
31.             }  
32.             else que.push(ii(v, u));  
33.         }  
34.   
35.     }  
36. }  
37.   
38. int main()  
39. {  
40.     #ifdef LOCAL  
41.     freopen("d.txt", "r", stdin);  
42.     //freopen("d.out", "w", stdout);  
43.     int T = 4;  
44.     while(T--){  
45.     #endif // LOCAL  
46.     ios::sync_with_stdio(false); cin.tie(0);  
47.   
48.     int n, k, d, i, u, v, ans = 0;  
49.     cin >> n >> k >> d;  
50.     for(i = 1; i <= k; i++){  
51.         cin >> u;  
52.         que.push(ii(u, -1));  
53.     }  
54.     for(i = 1; i < n; i++){  
55.         cin >> u >> v;  
56.         sons[u].push_back(ii(v, i));  
57.         sons[v].push_back(ii(u, i));  
58.     }  
59.   
60.     bfs();  
61.     for(i = 1; i <= n; i++){  
62.         if(f[i]) ans++;  
63.     }  
64.     cout << ans << "n";  
65.     ans = 0;  
66.     for(i = 1; i <= n; i++){  
67.         if(f[i]){  
68.             if(ans) cout << " ";  
69.             ans++;  
70.             cout << i;  
71.         }  
72.     }  
73.   
74.   
75.     #ifdef LOCAL  
76.     for(i = 1; i <= n; i++) sons[i].clear();  
77.     memset(vis, false, sizeof vis);  
78.     memset(f, false, sizeof f);  
79.     cout << endl;  
80.     }  
81.     #endif // LOCAL  
82.     return 0;  
83. }  

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx