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

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

aoj2491~2500 - (2013/03/23 (土) 11:16:23) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*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";
+ }