程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3452 最小割樹形dp

hdu 3452 最小割樹形dp

編輯：C++入門知識

Bonsai

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 684 Accepted Submission(s): 347

Problem Description 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.
Input 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 u_i v_i w_i (where u_i, v_i ∈ {1,……, n} and 0 <= w_i <= 1000) indicating that vertex u_i is connected to vertex v_i by an undirected edge with weight w_i. The input file will not contain duplicate edges. The end-of-file is denoted by a single line containing "0 0".
Output For each input test case, print a single integer indicating the minimum total weight of edges that must be deleted in order to ensure that there exists no path from one of the original leaves to the root.
Sample Input

Sample Output

Source 2009 Stanford Local ACM Programming Contest

給定一棵樹，求最小花費使得根節點與葉子節點斷開。

兩種思路：樹形dp，dp[u]表示切斷以u為子樹的代價，

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/9 21:30:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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

第二種思路：最小割，源點向根節點連邊，容量inf，葉節點向匯點連邊，容量inf，把剩下的邊連雙向，根據最小割最大流定理，最大流等於最小割。
代碼：
/* ***********************************************
Author :rabbit
Created Time :2014/3/9 22:00:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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]edge[S[i]].cap)
				   temp=edge[S[i]].cap,id=i;
		    for( i=0;idep[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