HDU - 3586
Information Disturbing
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 5471 Accepted Submission(s): 1774
Problem Description
In the battlefield , an effective way to defeat enemies is to break their communication system.
The information department told you that there are n enemy soldiers and their network which have n-1 communication routes can cover all of their soldiers. Information can exchange between any two soldiers by the communication routes. The number 1 soldier is the total commander and other soldiers who have only one neighbour is the frontline soldier.
Your boss zzn ordered you to cut off some routes to make any frontline soldiers in the network cannot reflect the information they collect from the battlefield to the total commander( number 1 soldier).
There is a kind of device who can choose some routes to cut off . But the cost (w) of any route you choose to cut off can’t be more than the device’s upper limit power. And the sum of the cost can’t be more than the device’s life m.
Now please minimize the upper limit power of your device to finish your task.
Input
The input consists of several test cases.
The first line of each test case contains 2 integers: n(n<=1000）m(m<=1000000).
Each of the following N-1 lines is of the form:
ai bi wi
It means there’s one route from ai to bi(undirected) and it takes wi cost to cut off the route with the device.
(1<=ai,bi<=n,1<=wi<=1000)
The input ends with n=m=0.
Output
Each case should output one integer, the minimal possible upper limit power of your device to finish your task.
If there is no way to finish the task, output -1.
Sample Input
5 5
1 3 2
1 4 3
3 5 5
4 2 6
0 0
Sample Output
3
题目大意：要我们切断根节点与叶子节点的联系，并最小化最大值，并同时总和不超过指定的值。
比较明显的树形dp，然后我们 dp[x] 表示，切断x节点与x的叶子节点的最小总花费。
同时我们怎么最小化最大值呢？很明显的二分。我们二分最大值即可，令v是节点u的儿子节点，w为u到v的花费，那么我们的转移方程为：
if(w<=mid) dp[u]+=min(dp[v],w);//mid为二分的值
else dp[u]+=dp[v];
这样从根节点dfs即可。（注意特判叶子节点）
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
const int inf=0x3f3f3f3f;
int n,m,dp[N],mid;
vector<int> v1[N],v2[N];
void dfs(int x,int pre){
if(v1[x].size()==1&&pre!=-1){
dp[x]=inf; return ;
}
dp[x]=0;
for(int i=0;i<v1[x].size();i++){
if(v1[x][i]==pre) continue;
dfs(v1[x][i],x);
if(v2[x][i]<=mid) dp[x]+=min(dp[v1[x][i]],v2[x][i]);
else dp[x]+=dp[v1[x][i]];
}
}
int check(){
dfs(1,-1); return (dp[1]<=m);
}
int bsearch(int l,int r){
int res=-1;
while(l<=r){
mid=l+r>>1;
if(check()){
res=mid; r=mid-1;
}
else l=mid+1;
}
return res;
}
signed main(){
while(cin>>n>>m,n||m){
for(int i=1;i<=n;i++) v1[i].clear(),v2[i].clear(); int r=0;
for(int i=1;i<n;i++){
int a,b,c; cin>>a>>b>>c; r=max(r,c);
v1[a].push_back(b); v2[a].push_back(c);
v1[b].push_back(a); v2[b].push_back(c);
}
cout<<bsearch(1,r)<<endl;
}
return 0;
}
