Information Disturbing
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3586
题意：
在战场上有n个地方据点，它们的通信网络构成一棵树，其根节点1为敌方指挥处，所有叶子节点为前线，每一条边存在一个权值wi表示切断这条线路需要花费wi，现需要你切断所有前线与指挥处的通信，切断线路的单次花费不得超过limit，求在总费用不超过m（m小于等于1000000）的情况下limit的最小值
题解：
一个水题，二分limit求最小花费是否小于m就行了
代码
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int N=1001;
struct node
{
int to,cost;
node(int x=0,int y=0)
{
to=x,cost=y;
}
};
bool mark[N];
int mmin(int x,int y)
{
return x<y?x:y;
}
vector<node>q[N];
int Dfs(int id,int cost,int lim,int m)
{
int sum=-1;
mark[id]=true;
for(int i=0;i<q[id].size();++i)
{
int v=q[id][i].to;
if(mark[v])continue;
int w=q[id][i].cost;
int u=Dfs(v,w,lim,m);
if(u==-1)return cost>lim?-1:cost;
sum+=u;
}
if(sum==-1)return cost>lim?-1:cost;
if(id==1)return sum+1>m?-1:sum+1;
return cost>lim?sum+1:mmin(cost,sum+1);
}
void bs(int m)
{
int l=0,r=m,res=-1;
while(l<=r)
{
memset(mark,false,sizeof(mark));
int mid=(l+r)/2;
if(Dfs(1,-1,mid,m)==-1)l=mid+1;
else r=mid-1,res=mid;
}
printf("%d
",res);
}
void solve()
{
int n,m,a,b,c;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
for(int i=1;i<=n;++i)
q[i].clear();
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&a,&b,&c);
q[a].push_back(node(b,c));
q[b].push_back(node(a,c));
}
bs(m);
}
}
int main()
{
solve();
return 0;
}