首页 > ACM题库 > HDU-杭电 > HDU 3452-Bonsai-动态规划-[解题报告]HOJ
2014
03-23

HDU 3452-Bonsai-动态规划-[解题报告]HOJ

Bonsai

问题描述 :

After being assaulted in the parking lot by Mr. Miyagi following the "All Valley Karate Tournament", John Kreese has come to you for assistance. Help John in his quest for justice by chopping off all the leaves from Mr. Miyagi’s bonsai tree!
You are given an undirected tree (i.e., a connected graph with no cycles), where each edge (i.e., branch) has a nonnegative weight (i.e., thickness). One vertex of the tree has been designated the root of the tree.The remaining vertices of the tree each have unique paths to the root; non-root vertices which are not the successors of any other vertex on a path to the root are known as leaves.Determine the minimum weight set of edges that must be removed so that none of the leaves in the original tree are connected by some path to the root.

输入:

The input file will contain multiple test cases. Each test case will begin with a line containing a pair of integers n (where 1 <= n <= 1000) and r (where r ∈ {1,……, n}) indicating the number of vertices in the tree and the index of the root vertex, respectively. The next n-1 lines each contain three integers ui vi wi (where ui, vi ∈ {1,……, n} and 0 <= wi <= 1000) indicating that vertex ui is connected to vertex vi by an undirected edge with weight wi. The input file will not contain duplicate edges. The end-of-file is denoted by a single line containing "0 0".

输出:

The input file will contain multiple test cases. Each test case will begin with a line containing a pair of integers n (where 1 <= n <= 1000) and r (where r ∈ {1,……, n}) indicating the number of vertices in the tree and the index of the root vertex, respectively. The next n-1 lines each contain three integers ui vi wi (where ui, vi ∈ {1,……, n} and 0 <= wi <= 1000) indicating that vertex ui is connected to vertex vi by an undirected edge with weight wi. The input file will not contain duplicate edges. The end-of-file is denoted by a single line containing "0 0".

样例输入:

15 15
1 2 1
2 3 2
2 5 3
5 6 7
4 6 5
6 7 4
5 15 6
15 10 11
10 13 5
13 14 4
12 13 3
9 10 8
8 9 2
9 11 3
0 0

样例输出:

16

/* ***********************************************
Author :rabbit
Created Time :2014/3/9 21:30:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=2020;
int head[maxn],tol;
struct Edge{
    int next,to,val;
}edge[10*maxn];
void add(int u,int v,int w){
    edge[tol].to=v;
    edge[tol].next=head[u];
    edge[tol].val=w;
    head[u]=tol++;
}
int dp[maxn];
void dfs(int u,int fa){
    int d=0;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        dfs(v,u);
        d+=min(dp[v],edge[i].val);
    }
    if(d)dp[u]=d;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,r;
     while(~scanf("%d%d",&n,&r)&&(n||r)){
         memset(head,-1,sizeof(head));tol=0;
         for(int i=1;i<n;i++){
             int j,k,m;
             scanf("%d%d%d",&j,&k,&m);
             add(j,k,m);
             add(k,j,m);
         }
         memset(dp,0x3f,sizeof(dp));
         dfs(r,-1);
         if(n==1)puts("0");
         else cout<<dp[r]<<endl;
     }
     return 0;
}
/* ***********************************************
Author :rabbit
Created Time :2014/3/9 22:00:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 10000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=2010;
const int maxm=1002000;
struct Edge{
	int next,to,cap;
	Edge(){};
	Edge(int _next,int _to,int _cap){
		next=_next;to=_to;cap=_cap;
	}
}edge[maxm];
int head[maxn],tol,dep[maxn],gap[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0,Q[maxn];
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int sap(int s,int t,int N){
	int res=0;bfs(s,t);
	int cur[maxn],S[maxn],top=0,u=s,i;
	memcpy(cur,head,sizeof(head));
	while(dep[s]<N){
		if(u==t){
			int temp=INF,id;
		    for( i=0;i<top;i++)
			   if(temp>edge[S[i]].cap)
				   temp=edge[S[i]].cap,id=i;
		    for( i=0;i<top;i++)
			      edge[S[i]].cap-=temp,edge[S[i]^1].cap+=temp;
		    res+=temp;top=id;u=edge[S[top]^1].to;
		}
		if(u!=t&&gap[dep[u]-1]==0)break;
		for( i=cur[u];i!=-1;i=edge[i].next)
			if(edge[i].cap&&dep[u]==dep[edge[i].to]+1)break;
		if(i!=-1)cur[u]=i,S[top++]=i,u=edge[i].to;
		else{
			int MIN=N;
			for( i=head[u];i!=-1;i=edge[i].next)
				if(edge[i].cap&&MIN>dep[edge[i].to])
					MIN=dep[edge[i].to],cur[u]=i;
			--gap[dep[u]];++gap[dep[u]=MIN+1];
			if(u!=s)u=edge[S[--top]^1].to;
		}
	}
	return res;
}
int in[maxn];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,r;
	 while(~scanf("%d%d",&n,&r)&&(n||r)){
		 memset(head,-1,sizeof(head));tol=0;
		 int sum=0;
		 memset(in,0,sizeof(in));
		 for(int i=1;i<n;i++){
			 int j,k,m;
			 scanf("%d%d%d",&j,&k,&m);
			 addedge(j,k,m);
			 addedge(k,j,m);
			 sum+=m;in[j]++;in[k]++;
		 }
		// for(int i=1;i<=n;i++)cout<<in[i]<<" ";cout<<endl;
		 for(int i=1;i<=n;i++){
			 if(i==r)addedge(0,r,INF);
			 else if(in[i]==1)addedge(i,n+1,INF);
		 }
		 int ans=sap(0,n+1,3*n);
		 cout<<ans<<endl;
	 }
     return 0;
}

参考:http://blog.csdn.net/xianxingwuguan1/article/details/20869207


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。