首页 > 代码库 > 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);}