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;
}