※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「aoj2491~2500」の編集履歴(バックアップ)一覧に戻る
aoj2491~2500」を以下のとおり復元します。
*aoj2491 sanpo
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2491
ねこのそらの散歩を題材にした問題。

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

この問題はすこし変わった方法で解けそうです。
ある枝に親猫がいて、その枝先のあるほうを調べるとします。
ある枝からその先に向けて、架空の探索猫を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";
 }   

復元してよろしいですか?