「aoj2491~2500」の編集履歴(バックアップ)一覧に戻る

aoj2491~2500 - (2013/03/24 (日) 15:58:31) の編集履歴(バックアップ)


aoj2491 sanpo

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2491
ねこのそらの散歩を題材にした問題。

解法
正答者数も少なく難しい問題です。
普通に探索しては小さなグラフでも間に合いません。
道を通った回数、今いる地点、残り時間の3種類を基準に点をプロットし、グラフとして素朴な動的計画法で解こうととすると点の数が膨大になります。

この問題はすこし変わった方法で解けそうです。
1番にタイムとそのタイムで得られる最大の価値の対応表を持った猫を待機させます。
その猫からどれかの道にむけて架空の探索猫を1匹先行させます。
探索猫は枝先でないならついた広場で待機し親猫となり、さらに子となる探索猫を一匹出します。
探索猫が枝先の広場にいるなら、その広場に至る道を何度か往復してこのタイムならこれだけの価値が得られるという情報の一覧を親猫に持ち帰ります。
その結果より良い結果があれば親猫はタイムと価値の対応表を更新します。
更新したタイムと価値の対応表を持たせて自分の持ち場の次の枝に探索猫を出し探索猫はその表を使ってその道の先から得られるタイムと価値の対応表を作ります。
全ての枝を検証し終わったら親猫は自分の親猫に一番良い結果を返し最後に1番が集計します。
後はスピードを上げるために往復の検証順序を価値の高い順にソートしておきます。


#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<string.h>
#include<algorithm>
struct Way{
	int to;
	long long int t,m,v;
};
struct S{ 
	 long long int v,t;
	bool operator<(const S& s)const{
		return t>s.t;
	}
};

const int size=301;
const int tMax=10001;

std::vector<Way> G[size];
long long int values[size][tMax];
void saiki(int parent,int now,Way w1,int T){
	int t1;
	long long int v1;
	if(parent!=0){
		std::vector<S> tempV;
		S s1;
		for(int i=0;i<=T;i+=2){
			s1.t=i;
			s1.v=values[parent][i];
			if(s1.v!=-1)tempV.push_back(s1);
		}
		std::sort(tempV.begin(),tempV.end());
		for(int i=0;i<tempV.size();i++){
			long long int baseV=tempV[i].v;
			for(long long int j=2;j<=w1.m+1+(w1.m==0);j+=2){
				t1=j*w1.t+tempV[i].t;
				if(t1>T)break;
 				v1=(j>=w1.m?w1.m:j)*w1.v+baseV;
				if(values[now][t1]<v1)values[now][t1]=v1;
				else break;
			}
		}
	}
	for(int i=0;i<G[now].size();i++){
		w1=G[now][i];
		if(parent!=w1.to){
			saiki(now,w1.to,w1,T);
			for(int j=0;j<=T;j++){
				if(values[now][j]<values[w1.to][j])values[now][j]=values[w1.to][j];
			}
		}
	}
}
 
int main(){
	int N,T,a,b;
	Way w1;
	long long int t1,m1;
	memset(values,-1,sizeof(values));
	
	scanf("%d %d",&N,&T);
	T=T-T%2;
	for(int i=0;i<N-1;i++){
		scanf("%d %d",&a,&b);
		std::cin>>w1.t>>w1.m>>w1.v;
		w1.to=b;
		G[a].push_back(w1);
		w1.to=a;
		G[b].push_back(w1);
	}
	values[1][0]=0;
	saiki(0,1,w1,T);
	long long int ans=0;
	for(int i=0;i<=T;i+=2){
		if(values[1][i]>ans)ans=values[1][i];
 	}
std::cout<<ans<<"\n";
}