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

aoj2491~2500 - (2013/03/24 (日) 15:54:07) の1つ前との変更点

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

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

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