洛谷 P2279 [HNOI2003]消防局的设立

看了下题解,用贪心写的。动规真心不会。贪心还凑和。
参见题解:https://waautomaton.blog.luogu.org/solution-p2279

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<int> edges[1005];
int depth[1005],father[1005],grandfather[1005];
struct node{
    int i,dep;
    node(int ii,int depp){i=ii;dep=depp;}
    bool operator < (const node& n2) const{
        return dep<n2.dep;
    }
};
priority_queue<node> pq;
bool visited[1005];
void dfsRange2(int pos,int dep){
//为什么这里不能发现visited之后就return呢,是因为有可能一个点虽被visited,但其周围的点未被扩展完全,所以其实visited在这里面没有任何作用,如果把注释去掉是20分的。
    //if(visited[pos])return;
    visited[pos]=true;
    if(dep==2)return;
    for(int i=0;i<edges[pos].size();i++){
        //if(visited[edges[pos][i]])continue;
        dfsRange2(edges[pos][i],dep+1);
    }
}
void dfsAll(int pos,int f,int gf,int dep){
    if(visited[pos])return;
    visited[pos]=true;
    father[pos]=f;
    grandfather[pos]=gf;
    depth[pos]=dep;
    for(int i=0;i<edges[pos].size();i++){
        if(visited[edges[pos][i]])continue;
        dfsAll(edges[pos][i],pos,f,dep+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++){
        int v;
        cin>>v;
        edges[i].push_back(v);
        edges[v].push_back(i);
    }
    memset(visited,false,sizeof(visited));
    dfsAll(1,1,1,1);
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++)pq.push(node(i,depth[i]));
    int cnter=0;
    while(!pq.empty()){
        if(visited[pq.top().i]){
            pq.pop();
            continue;
        }
        node cur=pq.top();pq.pop();
        dfsRange2(grandfather[cur.i],0);
        cnter++;
    }
    cout<<cnter;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注