hdu 3586 Information Disturbing (树形dp+二分)

Information Disturbing

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1722    Accepted Submission(s): 641

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⑴ 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.

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⑴ 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.
The input ends with n=m=0.

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 ⑴.

Sample Input
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » hdu 3586 Information Disturbing (树形dp+二分)


Hi, 如果你对这款模板有疑问,可以跟我联系哦!

赞助VIP 享更多特权,建议使用 QQ 登录