Hdu 3586 Information Disturbing 树型DP 删边

Information Disturbing

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 2940    Accepted Submission(s): 1058

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  

删边类树型DP。

给你一棵树，每条边有一个权值，删去若干条边的代价是删去所有边权值的和。要求删一些边使所有叶子不能到达根，并且代价和不超过m、所有删去的边的最大权值不超过k，求k最小是多少。

时限给了3s，而n只有1000，可以考虑二分答案。

这样，对于确定的k，我们只要使花费最小。

对任意一个叶子节点，要切断它与根的联系，只要切断它与根的路径上任意一条边即可。

用dp[i]表示对于i号节点，要切断它的子树上叶子与根的联系，只删去它子树的边的最小花费。

这样，对于指定的节点，由于只考虑切子树上的边，一共只有两种情况：

对于它的儿子节点，要么切断它与儿子之间的边，要么在它儿子节点的子树上切。

如果在儿子节点的子树上切，递归可得代价就是dp[son]。

如果切与儿子的边，代价就是这条边的权值。

最后，dp[i]=sum(min(dp[son],edge[i,son])) son表示 i 的儿子节点，只要有一个儿子没办法切，就失败了。

748ms AC

挖坑：等到树型DP刷得足够多，写个总结吧

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=1005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f; 
const ld pi=acos(-1.0L);
int num,m;
int dp[maxn],head[maxn];
bool visit[maxn];

struct Edge {
	int from,to,dist,pre;
};
Edge edge[maxn*2];

void addedge(int from,int to,int dist) {
	edge[num]=(Edge){from,to,dist,head[from]};
	head[from]=num++;
	edge[num]=(Edge){to,from,dist,head[to]};
	head[to]=num++;
}

bool dfs(int now,int md) {
	dp[now]=0;
	visit[now]=1;
	bool f=true;
	for (int i=head[now];i!=-1;i=edge[i].pre) {
		int to=edge[i].to;
		if (!visit[to]) { 
		    int p=inf; 
			if (dfs(to,md)) p=min(p,dp[to]); 
			if (edge[i].dist<=md) p=min(p,edge[i].dist);
			if (p==inf) f=false; else dp[now]+=p;
		}
	}
	if (now==1) {
		if (!f) return false; else return true;
	}
	if (dp[now]==0||!f) return false; else return true;
	return true;
}

int solve(int n) {
	int l=1,r=1000,mid,ans=-1;
	while (l<=r) {
		mid=(l+r)/2;
		mem0(visit);
		if (dfs(1,mid)) {
			if (dp[1]<=m) {
				ans=mid;
				r=mid-1;
			} else l=mid+1;
		} else l=mid+1;
	}
	return ans;
}

int main() {
	int n;
	scanf("%d%d",&n,&m);
	while (n!=0||m!=0) {
		num=0;
		memset(head,-1,sizeof(head));
		int i,j,x,y,d;
		for (i=1;i<n;i++) {
			scanf("%d%d%d",&x,&y,&d);
			addedge(x,y,d);
		}
		int ans=solve(n);
		printf("%d\n",ans);
		scanf("%d%d",&n,&m);
	}
	return 0;
}