P3557 [POI2013]GRA-Tower Defense Game

先看题目吧

有一个n个点m条边的图，每条边距离是1，已知用k个攻击距离为1的塔可以打到整个地图，让构造一个方案使得用小于等于k个攻击距离为2的塔打到整个地图

一开始，我以为这题很麻烦，后来仔细研究研究，才发现有些简单，这里面的k仅仅起到一个启发的作用，我们只要大胆地做，只要脸不是太黑就能过

思路：枚举每个点，如果该点已被覆盖，就在该点建造攻击塔，并向外延伸 2 的距离，对途中经过的点做标记，bfs两层

#include <bits/stdc++.h>
#define ll long long 
#define E 500007
using namespace std ; 
ll read() { ll aa ; cin >> aa ; return aa ; }
ll n , m , k , head[E] , q ; 
struct edge { ll pre , to ; } bian[E << 2] ; 
void add(ll u , ll v) {
    bian[++q].pre = head[u] ; 
    bian[q].to = v ; 
    head[u] = q ; 
}
ll ans[E] , rt ; 
bool vis[E] ; 
void gai(ll u , ll fath , ll dep) {
    vis[u] = 1 ; 
    if(dep == 0) return ; 
    for(int i = head[u] ; i ; i = bian[i].pre) {
        ll v = bian[i].to ; 
        if(v == fath) continue ; 
        gai(v , u , dep-1) ; 
    }
}
int main() {
    n = read() , m = read() , k = read() ; 
    for(int i = 1 , xi , yi ; i <= m ; i ++) {
        xi = read() , yi = read() ;
        add(xi , yi) , add(yi , xi) ; 
    }
    for(int i = 1 ; i <= n ; i ++) {
        if(vis[i]) continue ; 
        ans[++rt] = i ; 
        gai(i , 0 , 2) ;
    }
    cout << rt << endl ; 
    for(int i = 1 ; i <= rt ; i ++) cout << ans[i] << ' ' ; 
    return 0 ; 
}

P3557 [POI2013]GRA-Tower Defense Game

原文：https://www.cnblogs.com/trouble-faker/p/10357465.html