---恢复内容开始---
【问题描述】
在一片草原上有N个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张N个点、M条边的无向连通图，而度数大于2的点至多有1个。
兔子们决定把其中K个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。
【输入】
第一行有3个整数N，M，K，分别表示兔子窝的个数、路径数、计划建造的避难所数。
接下来M行每行三个整数x,y，表示第x个兔子窝和第y个兔子窝之间有一条路径相连。任意两个兔子窝之间至多只有1条路径。
【输出】
一个整数，表示最后一只到达避难所的兔子花费的最短时间。
【输入输出样例1】
| rabbit.in | rabbit.out |
| 5 5 2 1 2 2 3 1 4 1 5 4 5 | 1 |
见选手目录下的rabbit / rabbit1.in与rabbit / rabbit1.out
【输入输出样例1说明】
在第2个和第5个兔子窝建造避难所，这样其它兔子窝的兔子最多只需要经过1条路径就可以到达某个避难所。
【输入输出样例2】
见选手目录下的rabbit / rabbit2.in与rabbit / rabbit2.out
【数据规模与约定】
对于30%的数据，N≤15，K≤4；
对于60%的数据，N≤100；
对于100%的数据，1≤K≤N≤1,000，1≤M≤1,500
1 /* 2 求到达时间最晚的兔子的最早到达时间 3 二分答案X，求解至少建几个避难所，使得每个兔窝在距离X的范围内至少有一个避难所 4 枚举住在“根”的兔子去往的避难所的位置，记为A 5 令与A距离不超过X的兔子都前往A 6 剩下的兔窝被分成若干条链，容易计算最少需要建立几个避难所 7 判断总数是否超过K个 8 避难所数量可以少于k个 9 */ 10 #include11 #include 12 #include 13 #include 14 #define sc(x) scanf("%d",&x) 15 #define man 1000000 16 #define mem(x) memset(x,0,sizeof(x)) 17 using namespace std; 18 struct edge 19 { 20 int next,to; 21 }r[man<<2]; 22 struct road 23 { 24 bool circle; 25 int len; 26 }d[man]; 27 int num=0,head[man<<2],du[man],root,t0; 28 int cnt=0,ans=0; 29 int n,m,k; 30 bool vis[man]; 31 void add(int from,int to) 32 { 33 r[++num].next=head[from]; 34 r[num].to=to; 35 head[from]=num; 36 } 37 void dfs(int x) 38 { 39 vis[x]=1; 40 ++d[cnt].len; 41 for(int i=head[x];i;i=r[i].next) 42 { 43 if(vis[r[i].to]==0) 44 dfs(r[i].to); 45 else if(r[i].to==root&&x!=t0) 46 d[cnt].circle=1; 47 } 48 } 49 int calc(int len,int t)//计算此链上还需几个避难所 50 { 51 if(len<=0)return 0; 52 return (len-1)/(t*2+1)+1; 53 /* 54 len-1：数轴上表示1 2 3 4 5 6中间有五段，令t为1 时，len 为3至6那一段，但3属于前一段，应该计算的是4至6 的这一段 ，所以len-1。 55 t*2+1：数轴1 2 3 4 5 6 应计算4至6的一段，t*2表示5左右两个端点之间的距离（表示只有4和6两个点），并没有将5算进去，5也属于这一段， 56 所以+1是加上避难所本身自身这个点。 57 */ 58 } 59 bool check(int t) 60 { 61 int md=1000000; 62 for(int i=1;i<=cnt;i++) 63 { 64 for(int kp=0;kp<=d[i].len&&kp<=t;kp++)//当前链上的第一个避难所（root节点上的兔子会去的那个） 65 { 66 int tot; 67 if(!d[i].circle) 68 tot=calc(d[i].len-kp-t,t);//若为链 69 else tot=calc(d[i].len-kp-t+kp-t,t);//若为环 70 ++tot;//加上第一个避难所 71 for(int j=1;j<=cnt;j++) 72 if(j!=i) 73 { 74 if(!d[j].circle) 75 tot+=calc(d[j].len+kp-t,t);//注意A对他的影响 76 else tot+=calc(d[j].len+(kp-t)+(kp-t),t); 77 } 78 md=min(md,tot); 79 } 80 } 81 return md<=k; 82 } 83 int main() 84 { freopen("rabbit.in","r",stdin); 85 freopen("rabbit.out","w",stdout); 86 sc(n);sc(m);sc(k); 87 memset(du, 0, sizeof(du)); 88 for(int i=1;i<=m;i++) 89 { 90 int a,b; 91 sc(a);sc(b); 92 du[a]++;du[b]++; 93 if(du[a]>2)root=a; 94 if(du[b]>2)root=b;//寻找A 95 add(a,b); 96 add(b,a); 97 } 98 cnt=1;//从根伸出去的链+环的数量 99 mem(vis); 100 vis[root]=1; 101 for(int i=head[root];i;i=r[i].next) 102 { 103 t0=r[i].next;//用于判环 104 d[cnt].circle=0;//是否在环中 105 d[cnt].len=0;//此链Or环的长度（可以想成是点的数量） 106 dfs(t0); 107 ++cnt; 108 } 109 int l = 0, r = n;//二分答案（最少时间） 110 while (l < r) 111 { 112 int mid = (l + r) >> 1; 113 if (check(mid)) r = mid; 114 else l = mid + 1; 115 } 116 printf("%d\n", r); 117 return 0; 118 }
---恢复内容结束---