【APIO2010】巡逻
标签：space 难点 情况 span swa 最小 nod return 基础
这是一道关于树的直径的好题，值得一刷。
本题有两个难点，一个是分类讨论k，另一个是代码的实现（其实还好）。
本题k可以为1或2，因此我们分类讨论一下。
- 当k=1时，我们可以任选两个点连接，假设我们一条边都不连接，那么我们需要走2*m次，其中m为边的数量。假设我们在x,y上连一条边，那么我们用1个距离节省了dis(x,y)个距离，为了使答案最小化，我们要使dis(x,y)最大，显然我们求一遍树的直径即可，那么答案为2*m-zhijing+1.
- 当k=2时，就是在k=1的基础上再加上一条边，同样我们分成两部分讨论。假设这一个环与上一个环没有重合的边，那么问题很简单，只需要在上一个答案的基础上再减去dis(x,y)再+1即可。若这个环与上一个环有重合的部分，为了保证每一条边都被巡逻，那么我们发现重合的这部分需要走两次，环上剩下的部分走一次即可。这是我们把第一次求的直径上的边权都赋值为-1，然后再做一遍树的直径得到的答案就是第二次的解，所以这种情况的答案就是2*m-(zhijing1-1)-(zhijing2-1)=2*m-zhijing1-zhijing2+2.如果对于两个环没有重合的情况，这个答案依然成立。
我们先进行两次bfs求出树的直径，在bfs的同时记录在直径上与每一个点的相连的边，方便之后赋值-1，之后再进行一次树形dp求出树的直径即可。
1 #include 2 #include 3 #include 4 #include 5 using namespace std;
6 inline int read() {
7 int ret=0;
8 int op=1;
9 char c=getchar();
10 while(c‘0‘||c>‘9‘) {if(c==‘-‘) op=-1; c=getchar();}
11 while(c‘9‘&&c>=‘0‘) ret=ret*10+c-‘0‘,c=getchar();
12 return ret*op;
13 }
14 struct node {
15 int next,to,dis;
16 }a[1000101];
17 int n,head[1000101],num=1,k,dis[100010],pre[100010],ret,x,maxx;
18 queueint> q;
19 inline void add(int from,int to,int dis=1) {
20 a[++num].next=head[from];
21 a[num].to=to;
22 a[num].dis=dis;
23 head[from]=num;
24 }
25 int bfs(int s) {
26 while(!q.empty()) q.pop();
27 memset(dis,0x3f,sizeof(dis));
28 dis[s]=pre[s]=0;
29 q.push(s);
30 while(!q.empty()) {
31 int now=q.front();
32 q.pop();
33 for(int i=head[now];i;i=a[i].next) {
34 int v=a[i].to;
35 if(dis[v]==0x3f3f3f3f) {
36 dis[v]=dis[now]+a[i].dis;
37 pre[v]=i;
38 q.push(v);
39 }
40 }
41 }
42 int y=1;
43 for(int i=1;i)
44 if(dis[i]>dis[y]) y=i;
45 return y;
46 }
47 int zhijing() {
48 ret=bfs(1);
49 ret=bfs(ret);
50 return dis[ret];
51 }
52 int dp(int u,int fa) {
53 int sum1=0,sum2=0;
54 for(int i=head[u];i;i=a[i].next) {
55 int v=a[i].to;
56 if(v==fa) continue ;
57 sum2=max(sum2,dp(v,u)+a[i].dis);
58 if(sum2>sum1) swap(sum2,sum1);
59 }
60 maxx=max(maxx,sum1+sum2);
61 return sum1;
62 }
63 int main() {
64 n=read(); k=read();
65 for(int i=1;i) {
66 int x=read(),y=read();
67 add(x,y);
68 add(y,x);
69 }
70 x=zhijing();
71 if(k==1) {
72 printf("%d\n",2*(n-1)-x+1);
73 return 0;
74 }
75 while(pre[ret]) {
76 a[pre[ret]].dis=a[pre[ret]^1].dis=-1;
77 ret=a[pre[ret]^1].to;
78 }
79 dp(1,0);
80 printf("%d\n",2*n-x-maxx);
81 return 0;
82 }
AC Code
【APIO2010】巡逻
标签：space 难点 情况 span swa 最小 nod return 基础
原文地址：https://www.cnblogs.com/shl-blog/p/10799785.html
评论