http://www.lydsy.com/JudgeOnline/problem.php?id=2097

Time Limit:?10 Sec??Memory Limit:?64 MB
Submit:?417??Solved:?213
[Submit][Status][Discuss]

Description

Farmer John為了保持奶牛們的健康，讓可憐的奶牛們不停在牧場之間 的小路上奔跑。這些奶牛的路徑集合可以被表示成一個點集和一些連接 兩個頂點的雙向路，使得每對點之間恰好有一條簡單路徑。簡單的說來， 這些點的布局就是一棵樹，且每條邊等長，都為1。 對于給定的一個奶牛路徑集合，精明的奶牛們會計算出任意點對路徑的最大值， 我們稱之為這個路徑集合的直徑。如果直徑太大，奶牛們就會拒絕鍛煉。 Farmer John把每個點標記為1..V (2 <= V <= 100,000)。為了獲得更加短 的直徑，他可以選擇封鎖一些已經(jīng)存在的道路，這樣就可以得到更多的路徑集合， 從而減小一些路徑集合的直徑。 我們從一棵樹開始，FJ可以選擇封鎖S (1 <= S <= V-1)條雙向路，從而獲得 S+1個路徑集合。你要做的是計算出最佳的封鎖方案，使得他得到的所有路徑集合 直徑的最大值盡可能小。 Farmer John告訴你所有V-1條雙向道路，每條表述為：頂點A_i (1 <= A_i <= V) 和 B_i (1 <= B_i <= V; A_i!= B_i)連接。 我們來看看如下的例子：線性的路徑集合(7個頂點的樹) 1---2---3---4---5---6---7 如果FJ可以封鎖兩條道路，他可能的選擇如下： 1---2 | 3---4 | 5---6---7 這樣最長的直徑是2，即是最優(yōu)答案(當然不是唯一的)。

Input

* 第1行： 兩個空格分隔的整數(shù)V和S * 第2...V行： 兩個空格分隔的整數(shù)A_i和B_i

Output

* 第1行：一個整數(shù)，表示FJ可以獲得的最大的直徑。

Sample Input

7 2
6 7
3 4
6 5
1 2
3 2
4 5

Sample Output

2

HINT

Source

Gold

?

二分最小的直徑

驗證時，統(tǒng)計出每個節(jié)點所在鏈的長度，如果比當前ans大，就砍去、

1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 5 #define min(a,b) (a<b?a:b) 6 inline void read(int &x) 7 { 8 x=0; register char ch=getchar(); 9 for(; ch>'9'||ch<'0'; ) ch=getchar(); 10 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 11 } 12 13 const int N(1e5+5); 14 int n,p,u,v,s,t; 15 int head[N],sumedge; 16 struct Edge { 17 int v,next; 18 Edge(int v=0,int next=0):v(v),next(next){} 19 }edge[N<<1]; 20 inline void ins(int u,int v) 21 { 22 edge[++sumedge]=Edge(v,head[u]); 23 head[u]=sumedge; 24 edge[++sumedge]=Edge(u,head[v]); 25 head[v]=sumedge; 26 } 27 28 int l,r,mid,ans,tmp,cnt,td[N],dis[N]; 29 void DFS(int u,int fa,int num) 30 { 31 dis[u]=0; 32 for(int i=head[u]; i; i=edge[i].next) 33 if(edge[i].v!=fa) DFS(edge[i].v,u,num); 34 cnt=0; 35 for(int i=head[u]; i; i=edge[i].next) 36 if(edge[i].v!=fa) td[++cnt]=dis[edge[i].v]+1; 37 std::sort(td+1,td+cnt+1); 38 for(; cnt&&td[cnt]+td[cnt-1]>num; ) cnt--,tmp++; 39 dis[u]=td[cnt]; 40 } 41 bool check(int x) 42 { 43 tmp=0; DFS(1,0,x); 44 return tmp<=p; 45 } 46 47 int Presist() 48 { 49 // freopen("longnosee.in","r",stdin); 50 // freopen("longnosee.out","w",stdout); 51 52 read(n); read(p); 53 for(int u,v,i=1; i<n; ++i) 54 read(u),read(v),ins(u,v); 55 for(l=1,r=n; l<=r; ) 56 { 57 mid=l+r>>1; 58 if(check(mid)) 59 { 60 ans=mid; 61 r=mid-1; 62 } 63 else l=mid+1; 64 } 65 printf("%d\n",ans); 66 return 0; 67 } 68 69 int Aptal=Presist(); 70 int main(){;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Shy-key/p/7552943.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ——T 2097: [Usaco2010 Dec]Exercise 奶牛健美操的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。