Luogu T16048 会议选址

本题idea版权来自CSDN博客Steve_Junior的医院设置2。

并没有什么用的链接

题目背景

\(A\)国的国情十分独特。它总共有\(n\)个城市，由\(n-1\)条道路连接。国内的城市当然是连通的。

时隔多年，全国会议再次召开。全国人民欢欣雀跃，期待会议后国家发展揭开新篇章。然而，会议筹备组此时却在为会议选址问题头痛不已。

题目描述

为了响应“保护环境”的国策，中央决定不再将首都作为固定会址，而是先计算出全国每个城市参会代表人数\(p_i\)，若将城市u作为会址，定义城市v的出行开销为\(C_{v}=p_{v}*dis_{u,v}\)。会议筹备组的任务是选定一个城市\(u\)，使出行总开销\(\sum_{i=1}^{n}C_{i}\)最小。

输入格式

第一行一个数字\(n\)，表示城市总数。

第二行\(n\)个数字，表示每个城市参会代表人数。

第三行至第\(n+2\)行，每行三个数字\(u,v,w\)，表示一条权值为\(w\)的连接城市\(u\)与城市\(v\)的道路。

输出格式

一个数字，表示最小出行总开销。

数据范围

对于30%的数据，\(n\leq 200\)。

对于50%的数据，\(n\leq 1500\)。

对于100%的数据，\(n\leq 5\times 10^{5},1\leq w\leq 10^{4}\)。

题解

30分做法

floyd暴力求出任意点对之间的距离，枚举每个城市作为会址，计算出总开销之后取最小值。大概5分钟就可以写完。复杂度为\(O(n^3)\)。这也是对拍时std采用的做法。

50分做法

将暴力求任意点对之间距离的算法改为\(n\)次堆优化dijkstra算法就可以通过。或者也可以采用一遍DFS后暴力查询\(O(n^2)\)次LCA的做法。其实是为了强行凑部分分才这样设计的

100分做法

这个做法十分玄妙其实只是自己一开始nc了而已……。

下面到了精彩的猜结论时间

理性分析画图发现会址其实就是树的带权重心，与边权无关。

贴一个来自学弟的证明：

考虑这棵树中的某一条边\((u,v)\)，判断\(u\)和\(v\)哪个作为会址更优。可以看成城市\(u\)一侧的代表已经全部转移至城市\(u\)，城市\(v\)也是如此。此时不难发现，将会址设在两个城市中此时所处代表更多的那个城市，总开销是最小的。因此，每次会址向更优的方向调整时就会不断向树的带权重心靠近，最后带权重心就是会址。

带权重心的求法其实和不带权的没有什么区别。将节点数改成代表数就可以了。

找到带权重心之后，接下来的任务变成了快速求出总开销。这个可以用简单的树形DP实现。

以重心为全树的根节点，设计状态\(f_i\)为将以\(i\)为根节点的子树中所有节点转移至节点\(i\)的总开销，最后\(f_{root}\)就是答案。转移时，记\(v\rightarrow u\)为v是u的子节点，则\(f_{u}=\sum\limits_{v\rightarrow u}(f_{v}+size_{v}\cdot w_{u,v})\)。可以看作将已经转移至\(v\)的所有代表经过边\((u,v)\)转移至\(u\)。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10,maxm=2e5+10,inf=0x7fffffff;

int heade[maxn],dw[maxn],ev[maxm],ew[maxm],nexte[maxm];

int size[maxn],f[maxn],cost[maxn];

int n,tot=0,root,sum=0;

void add_edge(int u,int v,int w){ev[++tot]=v;ew[tot]=w;nexte[tot]=heade[u];heade[u]=tot;}

void getroot(int ui,int fa)

{

	int i,vi;

	size[ui]=dw[ui];f[ui]=0;

	for(i=heade[ui];~i;i=nexte[i])

	{

		vi=ev[i];if(vi==fa){continue;}

		getroot(vi,ui);size[ui]+=size[vi];

		f[ui]=max(f[ui],size[vi]);

	}

	f[ui]=max(f[ui],sum-size[ui]);

	if(f[ui]<f[root]){root=ui;}

}

void dfs(int ui,int fa)

{

	int i,vi,wi;

	size[ui]=dw[ui];cost[ui]=0;

	for(i=heade[ui];~i;i=nexte[i])

	{

		vi=ev[i];wi=ew[i];if(vi==fa){continue;}

		dfs(vi,ui);

		size[ui]+=size[vi];

		cost[ui]+=cost[vi]+size[vi]*wi;

	}

}

int main()

{

	int i,j,u,v,w;

	//freopen("data.in","r",stdin);

	//freopen("test.out","w",stdout);

	cin>>n;

	memset(heade,-1,sizeof(heade));

	for(i=1;i<=n;i++){scanf("%d",&dw[i]);sum+=dw[i];}

	for(i=1;i<n;i++){scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,w);}

	root=0;f[0]=inf;getroot(1,0);

	dfs(root,0);

	cout<<cost[root];

	return 0;

}

巴特西