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

题目链接：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;

}