首页 > 代码库 > BZOJ 1912 巡逻(树直径)
BZOJ 1912 巡逻(树直径)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1912
题意:给出一棵树,边权为1。现在加一条或两条边后,使得从1出发遍历每个点至少一次再回到1的路程最短。
思路:先求一次树的直径Max1。然后将直径的边权改为-1,再求一次直径Max2。答案为ans=(n-1)*2-(Max1-1)-(Max2-1)。
struct node{ int u,v,w,next;};node edges[N<<1];int head[N],e;void add(int u,int v,int w){ edges[e].u=u; edges[e].v=v; edges[e].w=w; edges[e].next=head[u]; head[u]=e++;}int n,m,Max;int son1[N],son2[N],f[N],p;void DFS(int u,int pre){ int i,v,w,x1=0,x2=0; for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; w=edges[i].w; if(v==pre) continue; DFS(v,u); if(f[v]+w>x1) x2=x1,son2[u]=son1[u],son1[u]=i,x1=f[v]+w; else if(f[v]+w>x2) x2=f[v]+w,son2[u]=i; } f[u]=x1; if(x1+x2>Max) Max=x1+x2,p=u;}int main(){ clr(head,-1); RD(n,m); int i,u,v; FOR1(i,n-1) { RD(u,v); add(u,v,1); add(v,u,1); } int ans=(n-1)<<1; clr(son1,-1); clr(son2,-1); Max=0; DFS(1,-1); ans-=Max-1; for(i=son1[p];i!=-1;i=son1[edges[i].v]) edges[i].w=edges[i^1].w=-1; for(i=son2[p];i!=-1;i=son1[edges[i].v]) edges[i].w=edges[i^1].w=-1; clr(son1,-1); clr(son2,-1); if(m>1) Max=0,DFS(1,-1),ans-=Max-1; PR(ans);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。