首页 > 代码库 > hdu4118(树形DP)

hdu4118(树形DP)

题意:给一棵树(每个节点是一个城市),每个节点上有一个人。每个人都要到另外一个城市,并且每个城市最后只能有一个人。问全局所有人旅行的最长的长度可以是多少。


解法:一定可以构造一种这样的情形:对于每条边,使得少的一边的所有人都到另一边去。这样就实现了每条边的最大化利用。一定是最优解。

代码:

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100100;
const int INF=1000000007;

struct edge
{
    int u,v;
    LL value;
    int next;
} edges[Max*2];
bool rem[Max];
int head[Max];
LL num[Max];
int tot=0;
void addedge(int u,int v,int value)
{
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].value=http://www.mamicode.com/value;>