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
Author
alpc86
Source
2010 ACM-ICPC Multi-University Training Contest（15）——Host by NUDT
题意：
给出N个节点，N-1条边的树，给出每条边权值w，现在要求切断其中一些边，使得任意一个叶子没有走到祖先（1）的路
给出m，要求切断的边的总权值小于等于m,求所有的方案中切断的最大的权最小的值
分析：
限制条件有3个：
1.每个叶子不能回到祖先
2.总花费不能超过m
3.求最大权的最小值
求最小值的话果断二分，枚举各个最大权，检查是否满足费用不超过m
其他就是切边，对于任意边，切or不切，决策果断用DP，又是在树上的DP，显然树形DP
dp[node]表示节点i切断与所有儿子的联系的最小花费，
切断与所有儿子的联系有2种情况：
1.直接切断 node 到 son的这条边 ，花费是 w(node,son)
2.儿子自身就与它自己的所有儿子切断了联系，花费是 dp[son]
状态转移：
if (w(node,son) <= limit) dp[node] += min(dp[son] , w(node,son)) //这条边可切断
else dp[node] += dp[son];//这条边不能切断
其中limit 是二分枚举的最大权，所以选择的w(node,son)不能超过这个limit
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int inf = 1000000 + 7;//开大了dp相加时会溢出 1000*1000
const int N = 1007;
int dp[N];
/*
dp[i]表示对于节点i，切断与所有儿子的联系的最小费用
切断与儿子的联系有两种方法：
1.直接切断 i - son 的边 花费 w(i,son)
2.让儿子切断与儿子的儿子的联系，即儿子无法接收到信息,花费 dp[son]
二分枚举 limit 找到满足费用小于等于m的最小limit
if (w(i,son) <= limit) dp[i] += min(dp[son] , w(i,son)) //这条边可切断
else dp[i] += dp[son]
*/
int e[N][N];
vector<int>s[N];
int n,m;
int limit;
void treedp(int node,int fa)
{
dp[node] = 0;bool leaf = 1;
for (int i = 0;i < s[node].size();++i)
{
int &son = s[node][i];
if (son == fa) continue;
leaf = 1;
treedp(son,node);
if (e[node][son] <= limit) dp[node] += min(dp[son],e[node][son]);
else dp[node] += dp[son];
}
if (leaf) dp[node] = inf;//叶子
}
bool ok()
{
treedp(1,0);
if (dp[1] > m) return 0;
else return 1;
}
int finds(int l,int r)
{
int ans = -1;
while (l <= r) //二分求最小值
{
int mid = (l+r)>>1;
limit = mid;
if (ok())
{
ans = limit;
r = mid-1;
}
else l = mid + 1;
}
return ans;
}
int main()
{
while (scanf("%d %d",&n,&m),m+n)
{
mem(s,0);mem(e,0);
int l = 1,r = 0;
for (int i = 1,u,v,w;i < n;++i)
{
scanf("%d %d %d",&u,&v,&w);
e[u][v] = e[v][u] = w;
s[u].push_back(v);
s[v].push_back(u);
r = max(r,w);
}
printf("%d\n",finds(l,r));
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1288223.html
