洛谷P3629 [APIO2010] 巡逻题解

题目链接

P3629 [APIO2010] 巡逻 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

n个村庄，n-1条道路，原图为树

1.若k=0（不修建道路）那么答案为（n-1）*2

 每个道路会走两遍

2.若k为1（修建一条道路）

设修建的道路（r1）所在的环长度为L

那么答案为（n-1）*2-L+2

可以看到r1所在环的道路只走了一次

所以答案为原答案-（环的长度-1（r1））-1（r1）

令答案最小，则是令环的长度最长

则道路应修建在直径的两个端点上

答案为（n-1）*2-直径的长度+1；

3.若k为2（修建2条道路）

由b、c可知（或者自己手推）两条道路所在环可能有公共边或无公共边

当无公共边时（如图b）

发现两条道路互不影响

当无公共边时（如图c）

由于要满足必须经过新建的道路正好一次，两个环重复的地方仍要经过两次

那么将第一次计算的直径所经过的边权变成-1，再第二次计算直径即可

综上

当k=1时ans=（n-1）*2-直径长+1；

当k=2时ans=（n-1）*2-第一次的直径长+1-第二次的直径长+1

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=100005;
 5 
 6 int head[N],ne[N*2],v[N*2],w[N*2],tot=0;//链式前向星存图
 7 void add(int x,int y,int z){
 8     ne[++tot]=head[x];
 9     v[tot]=y;
10     w[tot]=z;
11     head[x]=tot;
12 }
13 
14 
15 int l,ans=0;
16 int fa[N];//存每个节点的父亲
17 
18 void dfs(int u,int ffa,int dis){
19     if(dis>ans){
20         ans=dis;
21         l=u;
22     }
23     for(int i=head[u];i;i=ne[i]){
24         if(v[i]==ffa) continue;
25         fa[v[i]]=u;
26         dfs(v[i],u,dis+w[i]);
27     }
28 }
29 
30 int f[N][2];
31 void solve(int u,int ffa){
32     for(int i=head[u];i;i=ne[i]){
33         int v1=v[i];
34         if(v1==ffa) continue;
35         solve(v1,u);
36         if(f[v1][0]+w[i]>=f[u][0]){
37             f[u][1]=f[u][0];
38             f[u][0]=f[v1][0]+w[i];
39         }
40         else if(f[v1][0]+w[i]>f[u][1]) f[u][1]=f[v1][0]+w[i];
41     }
42 }
43 
44 int main(){
45     int n,k;
46     scanf("%d %d", &n, &k);
47     for(int i=1;i<n;i++){
48         int x,y;
49         scanf("%d %d", &x, &y);
50         add(x,y,1);
51         add(y,x,1);
52     }
53     
54     dfs(1,0,0);
55     for(int i=1;i<=n;i++) fa[i]=0;
56     ans=0;
57     dfs(l,0,0);
58     //从直径的一端开始，将构成直径的边赋值为-1
59     while(fa[l]){
60         for(int i=head[l];i;i=ne[i]){
61             if(v[i]==fa[l]){
62                 w[i]=-1;
63                 if(i%2==0) w[i-1]=-1;
64                 else w[i+1]=-1;
65                 break;
66             }
67         }
68         l=fa[l];
69     }
70     if(k==1){
71         cout<<(n-1)*2-ans+1;
72         return 0;
73     }
74     int l1=ans;
75     
76     solve(1,0);
77     
78     ans=0;
79     for(int i=1;i<=n;i++) ans=max(ans,f[i][0]+f[i][1]);
80     cout<<n*2-l1-ans;
81     
82     return 0;
83 }