POJ 1849 树的直径或者树形dp

Description

Input

Output

Sample Input

5 2
1 2 1
2 3 2
3 4 2
4 5 1

Sample Output

6

题意：有n个地区，n-1条边，有两辆车在某一个地方，他们要从起点出发，清扫所有的街道，就是树上的边，求最小路径。

咋一看，没思路，只能往树的直径上想，直接拿所有边的二倍-直径也能ac，不过不明白原理，无法证明正确性。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-6 4:48:24
File Name :3.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=100100;
int head[maxn],dis[maxn],tol,n;
struct node{
	int next,to,val;
	node(){};
	node(int _next,int _to,int _val):next(_next),to(_to),val(_val){}
}edge[3*maxn];
void add(int u,int v,int val){
	edge[tol]=node(head[u],v,val);
	head[u]=tol++;
}
int bfs(int &s){
	  memset(dis,-1,sizeof(dis));
	  dis[s]=0;
	  queue<int> q;
	  q.push(s);
	  while(!q.empty()){
		  int u=q.front();q.pop();
		  for(int i=head[u];i!=-1;i=edge[i].next){
			  int v=edge[i].to;
			  if(dis[v]!=-1)continue;
			  dis[v]=dis[u]+edge[i].val;
			  q.push(v);
		  }
	  }
	  int mx=0;
	  for(int i=1;i<=n;i++)
		  if(dis[i]>mx)mx=dis[i],s=i;
	  return mx;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,m,p;
	 while(~scanf("%d%d",&n,&m)){
		 memset(head,-1,sizeof(head));tol=0;
		 int sum=0;
		 for(k=1;k<n;k++){
			 scanf("%d%d%d",&i,&j,&p);
			 add(i,j,p);
			 add(j,i,p);
			 sum+=p;
		 }
		 int ans=bfs(m);
		  ans=bfs(m);
		 cout<<2*sum-ans<<endl;
	 }
     return 0;
}

下面是树形dp，dp[u][i]代表以u为根的子树有i辆车的代价，然后就是u与子节点背包跟新dp值的过程。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-6 5:53:24
File Name :3.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=100100;
int head[maxn],dp[maxn][3],tol;
struct node{
	int next,to,val;
	node(){};
	node(int _next,int _to,int _val):next(_next),to(_to),val(_val){}
}edge[3*maxn];
void add(int u,int v,int val){
	edge[tol]=node(head[u],v,val);
	head[u]=tol++;
}
void dfs(int u,int fa){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		int ret[3];
		for(int j=0;j<3;j++){
			 ret[j]=dp[u][j];
			 dp[u][j]=INF;
		}
		int tmp[3]={2*edge[i].val,edge[i].val,2*edge[i].val};
		for(int j=2;j>=0;j--)
			for(int k=0;k<=j;k++)
				dp[u][j]=min(dp[u][j],ret[j-k]+dp[v][k]+tmp[k]);
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,m,n,p;
	 while(~scanf("%d%d",&n,&m)){
		 memset(head,-1,sizeof(head));
		 tol=0;
		 for(i=1;i<n;i++){
			 scanf("%d%d%d",&j,&k,&p);
			 add(j,k,p);
			 add(k,j,p);
		 }
		 memset(dp,0,sizeof(dp));
		 dfs(m,-1);
		 int ans=INF;
		 for(i=0;i<3;i++)
			 ans=min(ans,dp[m][i]);
		 cout<<ans<<endl;
	 }
     return 0;
}

POJ 1849 树的直径或者树形dp

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18945567