【luogu P2279 [HNOI2003]消防局的设立】 题解

时间:2021-05-20 14:00:56

题目链接:https://www.luogu.org/problemnew/show/P2279

想怎么贪怎么贪

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int n, ans, dis[maxn], dep[maxn];
bool vis[maxn], vis1[maxn];
struct node{
int f, gf, deep;
}a[maxn<<2];
struct edge{
int len, next, from, to;
}e[maxn<<2];
int head[maxn], cnt;
void add(int u, int v)
{
e[++cnt].from = u;
e[cnt].next = head[u];
e[cnt].len = 1;
e[cnt].to = v;
head[u] = cnt;
}
void dfs(int u, int p, int d)
{
a[u].deep = d;
dep[u] = d;
a[u].f = p;
a[u].gf = a[a[u].f].f;
for(int i = head[u]; i != -1; i = e[i].next)
if(e[i].to != p) dfs(e[i].to, u, d+1);
}
void bfs(int s)
{
memset(vis, 0, sizeof(vis));
memset(dis, 127, sizeof(dis));
queue<int> q;
dis[s] = 0;
vis[s] = 1;
q.push(s);
while(!q.empty())
{
int now = q.front(); q.pop();
vis[now] = 0;
for(int i = head[now]; i != -1; i = e[i].next)
{
if(dis[e[i].to] > dis[now] + e[i].len)
{
dis[e[i].to] = dis[now] + e[i].len;
if(!vis[e[i].to])
{
vis[e[i].to] = 1;
q.push(e[i].to);
}
}
}
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d",&n);
for(int i = 2; i <= n; i++)
{
int u; scanf("%d",&u);
add(i, u), add(u, i);
}
dfs(1, 0, 1);
//sort(a+1, a+1+n, cmp);
/*for(int i = 1; i <= n; i++)
cout<<a[i].x<<" "<<"f:"<<a[i].f<<" gf:"<<a[i].gf<<" deep:"<<a[i].deep<<endl;*/
for(int i = 1; i <= n; i++)
{
int now = -1, maxx = -1;
for(int j = 1; j <= n; j++)
{
if(a[j].deep > maxx && vis1[j] == 0)
now = j, maxx = a[j].deep;
}
vis1[now] = 1;
bfs(a[now].gf);
for(int j = 1; j <= n; j++)
if(dis[j] <= 2) vis1[j] = 1;
if(now == -1) break;
ans++;
}
cout<<ans;
return 0;
}