首页 > 代码库 > 【bzoj1912】 Apio2010—patrol 巡逻

【bzoj1912】 Apio2010—patrol 巡逻

2024-08-16 05:46:17   220人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1912 (题目链接)

题意

　　给出一棵树，要求在树上添加K(1 or 2)条边，添加的边必须经过一次，使得从1号节点到达每个节点最后返回1号节点所经过的路径最短。

Solution

　　如果不添加边，那么答案一定是每条边经过两次。

　　如果K为1，那么答案就很明显对吧，找到树的直径，链接直径两端点，使得直径上的边只经过一次，答案最优。

　　那么如果K为2，我们会发现，当两个环有变重叠时，重叠的边同样是要经过2次。也就是说第一次添加边时构成的环上面的边，如果在第二次添加是仍在环上，那么并不会对答案有贡献。所以我们第二次添加边时，先将树的直径上的边的边权改为-1，之后跑一遍树上最长链(注意有负权，所以不能找树的直径)即可。

代码

// bzoj1912#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;struct edge {int to,next,w;}e[maxn<<1];int head[maxn],deep[maxn],rt[2],f[maxn][2],son[maxn];int n,k,cnt,p;void link(int u,int v) {	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=1;	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=1;}void dfs(int x,int fa) {	if (deep[rt[p]]<deep[x]) rt[p]=x;	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {			deep[e[i].to]=deep[x]+e[i].w;			dfs(e[i].to,x);		}}int work(int x,int fa) {	if (x==rt[1]) return 1;	for (int i=head[x];i;i=e[i].next)		if (e[i].to!=fa) if (work(e[i].to,x)) {				e[i].w=e[i&1?i+1:i-1].w=-1;				return 1;			}	return 0;}void dd(int x,int fa) {	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {			dd(e[i].to,x);			if (f[x][1]<f[e[i].to][1]+e[i].w) f[x][1]=f[e[i].to][1]+e[i].w,son[x]=e[i].to;			else f[x][0]=max(f[x][0],f[e[i].to][1]+e[i].w);		}	if (f[x][0]==-inf) f[x][0]=0;if (f[x][1]==-inf ) f[x][1]=0;}void dp(int x,int fa,int d) {	if (f[x][1]<d) f[x][0]=f[x][1],f[x][1]=d,son[x]=0;	else f[x][0]=max(f[x][0],d);	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {			if (son[x]==e[i].to) dp(e[i].to,x,e[i].w+f[x][0]);			else dp(e[i].to,x,e[i].w+f[x][1]);		}}int main() {	scanf("%d%d",&n,&k);	for (int u,v,i=1;i<n;i++) {		scanf("%d%d",&u,&v);		link(u,v);	}	dfs(1,0);deep[rt[p++]]=0;dfs(rt[0],0);	int ans=(n-1)*2-deep[rt[1]];	if (k==1) {printf("%d",ans+k);return 0;}	work(rt[0],0);	for (int i=1;i<=n;i++) f[i][0]=f[i][1]=-inf;	deep[1]=0;dd(1,0);	dp(1,0,-inf);	int tmp=0;	for (int i=1;i<=n;i++) tmp=max(tmp,f[i][1]);	printf("%d",ans-tmp+k);	return 0;}

　　

【bzoj1912】 Apio2010—patrol 巡逻


联系
我们