Hdu 4003 Find Metal Mineral(DP_ツリーDP(リュックサック))

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4003
1本のn個のノードの木を与えて、すべての数辺を遍歴してすべて費用costを必要として、今k個のロボットを与えて、このk個のロボットで全体の木を遍歴することを要求して、通る費用と最小にして、n<=100000.
问题解决の考え方:木型DP+パケットバックパック、本題のパケットバックパックは一般的に1つのものを多く選択するのではなく、1つを選択しなければならず、1つしか選択できないので、具体的には後で分析します.この問題は長い間考えていたが、最初は貪欲な解法を考えていたが、kが1であれば、葉から根までの費用と最大の経路を見つければいい.広げて前のk大の経路を見つけようとしても解けるのではないか.答えはNo、パスが重なるので仕方ありません.この考えは否定してから、动规の考えでこの问题を解くことを考え始めた.
     親ノードの状態がサブノードからのみ移行することから,この問題には後効性がなく,ツリーdpが利用できることが分かる.各ノードにはいくつかのサブノードがあり、各サブノードは0-j個のロボットを選択して歩くことができます(0の場合はこの分岐を歩くロボットが他の分岐を通ったことを示す)、これでモデルを変換することができ、どれだけのサブノードが何組のアイテムを持っているか、各サブノードが選択しなければならないので、各グループのアイテムは1つ選択しなければなりませんが、1つしか選択できません.明らかに!
     dpを設定[i][j]ノードiでj個のロボットでそのすべてのサブノードを遍歴するのにかかる最小費用を表します.各ノードが歩かなければならないため、各ノードがどのように歩くかには2つの状況があります.1つはロボットがこの点から戻ってこないことです.1つはロボットがこの点から戻ってきたことです.そのため、j=0とj>0で表します.いくつかのロボットがある分岐に入ってから戻ってくる場合ロボットが1匹しか戻ってこない.vノードから下りてきて、回ってきた4*p->v->cost+p->vをルートにした木を2匹、p->v->vost+p->vをルートにした木を1匹、例えば辺に(1,2)(2,3)(2,4)があり、1匹であれば1点に2回、2匹であれば(1,2)を4回回ったとする.
    状態遷移方程式は,dp[i][j]=min(dp[i][j-1]+dp[son][0]+cost,dp[i][j]+dp[son][0]+2*cost)である.
                          dp[i][j]=min(dp[i][j],dp[son][k]+dp[i][j-k]+k*cost);//costはエッジ(i,son)費用,kはサブノードの状態
    本題は典型的な木型DP+リュックサックで、よく吸収することを強くお勧めします.コードは絶えず最適化することができて、私のコードの中で状態の移行方程式は実はもっと簡単ですが、このようによく理解することを考えて、コードは234 ms走って、第1位の上位で、悪くありません.
テストデータ:
5 1 2 1 2 2 1 3 2 2 4 2 2 5 2 5 1 2 1 2 2 1 3 2 2 4 10 2 5 10 3 1 1 1 2 1 1 3 1 3 1 2 1 2 1 1 3 1 7 1 2 1 2 2 1 3 2 2 4 2 2 5 2 3 6 10 3 7 10 9 1 1 1 2 2 1 3 2 2 4 2 2 5 2 3 6 10 3 7 10 4 8 20 4 9 20
7 1 3
1 2 100 1 4 100 1 3 2 3 5 1 3 6 1 3 7 1 8 1 3 1 8 100 1 2 100 1 4 100 1 3 2 3 5 1 3 6 1 3 7 1 8 1 3 1 8 100 1 2 100 1 4 100 1 3 2 3 5 100 3 6 100 3 7 100 7 1 3 1 2 100 1 4 100 1 3 2 3 5 1000 3 6 100 3 7 1000
コード:

#include <stdio.h>
#include <string.h>
#define MAX 11000
#define min(a,b) (a)<(b)?(a):(b)


struct node {

	int v,cost;
	node *next;
}*head[MAX*2],tree[MAX*2];
int ptr,ans,root,vis[MAX];
int n,m,dp[MAX][12];


void Initial() {
	
	ptr = 1;
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	memset(head,NULL,sizeof(head));
}
void AddEdge(int x,int y,int cost) {

	tree[ptr].v = y,tree[ptr].cost = cost;
	tree[ptr].next = head[x],head[x] = &tree[ptr++];
	tree[ptr].v = x,tree[ptr].cost = cost;
	tree[ptr].next = head[y],head[y] = &tree[ptr++];
}
void Tree_DP(int v) {

	if (vis[v]) return;
	vis[v] = 1;
	int i,j,fir,sec;
	node *p = head[v];
	

	while (p != NULL) {

		if (!vis[p->v]) {

			Tree_DP(p->v);
			for (j = m; j >= 1; --j) {

				fir = dp[v][j-1] + dp[p->v][0] + p->cost;	//        p->v    ，fir、sec                
				sec = dp[v][j] + dp[p->v][0] + 2 * p->cost;	//           p->v    ，   1  
				dp[v][j] = min(fir,sec);
				for (i = 1; i <= j; ++i)
					dp[v][j] = min(dp[v][j],dp[p->v][i]+dp[v][j-i]+i*p->cost);
			}
			dp[v][0] += dp[p->v][0] + 2 * p->cost;			//         ，         ，              
		}
		p = p->next;
	}
}


int main()
{
	int i,j,k,a,b,c;
	

	while (scanf("%d%d%d",&n,&root,&m) != EOF) {

		Initial();
		for (i = 1; i < n; ++i) {

			scanf("%d%d%d",&a,&b,&c);
			AddEdge(a,b,c);
		}


		Tree_DP(root);
		printf("%d
",dp[root][m]);
	}
}

ZeroClockオリジナルですが、私たちは兄弟なので転載できます.