专栏文章

题解：P13918 [PO Final 2024] 雪崩 / Avalanche

ccengzh
P13918题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1o28a
此快照首次捕获于
2025/12/02 11:54
3 个月前
此快照最后确认于
2025/12/02 11:54
3 个月前
查看原文
第一步是问题转化。
我们知道村庄关系就是一棵树，那么破坏最大化一定是从树根开始雪崩，这样树的大小就是雪崩的破坏程度。而 kk 个点其实就是被删去的点，雪崩无法在这里发生也无法来到这里。
那么问题就转化成：给定一棵树，删去 kk 个点，使得最大的连通块大小最小。
求最大值最小问题首先想到二分答案。
不难发现 ansans 以上的答案是可以实现的，ansans 以下的答案无论如何无法实现。所以二分这个界限 ansans。
判断有无解很简单，贪心。记块大小的最大值为 mm，根据树的性质，我们自底向上遍历，求要删去的最少点数 cntcnt。
当前子树的大小超过 mm 时，我们不得不删去当前节点，并且该节点对于父节点大小的贡献是 00。由于我们自底向上实现，当前节点所有子树的大小一定不会超过 mm，所以此时删去该节点是最优的。
如果 cnt<kcnt < k，说明子树大小可以进一步宽松，否则一定无解。
CPP
# include <bits/stdc++.h>
# include <iostream>

using namespace std;

struct Node
{
  int to;
  struct Node* nxt;
};
struct Head
{
    struct Node* nxt;
};

struct Head p[100005];
int siz[100005];
int cnt;

struct Node* ini()
{
    struct Node* tmp = (struct Node*) malloc (sizeof(struct Node));
    tmp->nxt = NULL;
    return tmp;
}

void add_edge(int x,int y)
{
    struct Node* tmp1 = ini();
    tmp1->to = y;
    tmp1->nxt = p[x].nxt;
    p[x].nxt = tmp1;
    return ;
}

int solve(int u,int k)
{
	siz[u] = 1;
	for (struct Node* tmp=p[u].nxt;tmp!=NULL;tmp=tmp->nxt)
	{
		int v = tmp->to;
		solve(v,k);
		siz[u] += siz[v];
	}	
	if (siz[u] > k)
	{
		siz[u]=0;
		cnt++;
	}
	return siz[u];
}

int main (void)
{
	int n,k;
	scanf ("%d %d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		p[i].nxt = NULL;
	}
	for (int i=1;i<n;i++)
	{
		int u,v;
		scanf ("%d",&u);
		v=i+1;
		add_edge(u,v);
	}

	int l=1,r=n;
	int ans;
	while (l <= r)
	{
		cnt=0;
		int mid = (l+r)/2; // mid是最大破坏值 
		solve(1,mid);
		if (cnt > k) // solve得到的是最大破坏值的情况下最少需要几个围墙 
		{
			l = mid+1;
		}
		else
		{
			r = mid-1;
			ans = mid;
		}
	}
	printf ("%d",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...