hdu 3586 Information Disturbing （樹形dp+二分）
來源：程序員人生 發布時間：2015-06-12 08:54:55 閱讀次數：3165次
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.
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⑴ 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 ⑴.
Sample Input
5 5
1 3 2
1 4 3
3 5 5
4 2 6
0 0
Sample Output
刪除邊使樹根和每一個葉子節點斷開，斷開的邊權值盡可能小，且總權值和不大于m;
2分邊權值，在樹上進行動態計劃，求斷開后權值和最小值。
對每一個節點u，用dp[u]記錄斷開它所有子孫節點的最小權值和，
枚舉它的每個子節點，對當前子節點，斷開它的代價為dp[u]=min(dp[v],u-v邊的權值)；
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define ll long long
#define N 1100
#define mem(a,t) memset(a,t,sizeof(a))
const int inf=1000005;
struct node
{
int v,w,next;
}e[N*2];
int dp[N];
int head[N];
int vis[N];
int cnt,n;
void add(int u,int v,int w)
{
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
}
void tree_dp(int u,int limit)
{
int i,v,flag=0,tmp=0; //flag標記是不是是葉子節點
for(i=head[u];i!=⑴;i=e[i].next)
{
v=e[i].v;
if(!vis[v])
{
vis[v]=1;
flag=1;
tree_dp(v,limit);
if(e[i].w>limit) //當前邊權值大于限制，只能取dp[v]
tmp+=dp[v];
else //取最優解
tmp+=min(dp[v],e[i].w);
}
}
if(flag)
dp[u]=tmp;
else //葉子節點權值為inf
dp[u]=inf;
}
int main()
{
//freopen("in.txt","r",stdin);
int i,u,v,m,w;
int l,r,mid,ans;
while(scanf("%d%d",&n,&m),n||m)
{
mem(head,⑴);
cnt=0;
l=r=1;
for(i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
r=max(r,w);
}
ans=⑴;
while(l<=r)
{
mid=(l+r)>>1;
for(i=1;i<=n;i++)
vis[i]=dp[i]=0;
vis[1]=1;
tree_dp(1,mid);
if(dp[1]<=m)
{
r=mid⑴;
ans=mid;
}
else
l=mid+1;
}
printf("%d
",ans);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
