程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1849 樹的直徑或者樹形dp

POJ 1849 樹的直徑或者樹形dp

編輯：C++入門知識

Two Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1081 Accepted: 517

Description

The city consists of intersections and streets that connect them.

Heavy snow covered the city so the mayor Milan gave to the winter-service a list of streets that have to be cleaned of snow. These streets are chosen such that the number of streets is as small as possible but still every two intersections to be connected i.e. between every two intersections there will be exactly one path. The winter service consists of two snow plovers and two drivers, Mirko and Slavko, and their starting position is on one of the intersections.

The snow plover burns one liter of fuel per meter (even if it is driving through a street that has already been cleared of snow) and it has to clean all streets from the list in such order so the total fuel spent is minimal. When all the streets are cleared of snow, the snow plovers are parked on the last intersection they visited. Mirko and Slavko don’t have to finish their plowing on the same intersection.

Write a program that calculates the total amount of fuel that the snow plovers will spend.

Input

The first line of the input contains two integers: N and S, 1 <= N <= 100000, 1 <= S <= N. N is the total number of intersections; S is ordinal number of the snow plovers starting intersection. Intersections are marked with numbers 1...N.

Each of the next N-1 lines contains three integers: A, B and C, meaning that intersections A and B are directly connected by a street and that street's length is C meters, 1 <= C <= 1000.

Output

Write to the output the minimal amount of fuel needed to clean all streets.

Sample Input

Sample Output

題意：有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 
#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=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 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

下面是樹形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 
#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=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