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

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

AOJ2111~2120 - (2012/07/26 (木) 15:06:19) の編集履歴(バックアップ)


#
平面上に散らばってる線分を繋げて一本の長い折れ線を作るとき、最小の長さの折れ線を作った時の長さを答えよという問題。
プログラミングコンテストの過去問を1000問解いたって私のように学歴、職歴、実績ない3無い人間の私は何の評価もされません。
単なる趣味でしかありません。
使い捨て労働で仕事を探しながらこの趣味を完遂するのだけが楽しみです。
何かアプリでも作って売れたら世間からの評価も変わるかもしれないのでその可能性にかけるくらいです。


解法
さてこの問題は自分なりに考えた解法は以下の通りです。
単純に深さ優先探索を行うと線分が11本を超えたあたりで11!となり計算量が限界に近づきます。
分岐が不可能なのでプリム法も使えません。
よって動的計画法を使わなくてはいけません。
この問題は全ての線分の端からスタートします。
動的計画法では、memo[次に線分を繋げる点0か1][最後に繋げた線分][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。
で動的計画法を適用していくだけの簡単な問題です。
この問題は私はあまりいい解法ではなかったようです。
スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。




#include<stdio.h>
#include<queue>
#include<math.h>
#include<string.h>
struct State{
int nowNo,perm,r;//今いる地点と結んだ線分のリストのビット表現と次の向き
double len;//今まで引いた長さ
bool operator<(const State& s)const{
	return len>s.len;
}
};
double memo[2][14][2<<14];//[次の線分の出発点][最後に結んだ線分][結んだ線のビット表現]
bool   first[2][14][2<<14];//最初
void setData(int n,int i){
double xs[2][15],ys[2][15];
memset(first,true,sizeof(first));
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf",&xs[0][i],&ys[0][i],&xs[1][i],&ys[1][i]);
}
//printf("scanOK");

double lensMemo[2][2][15][15],len1;//線分で結ぶ時の距離のメモ
for(int l1=0;l1<n;l1++){
	for(int l2=0;l2<n;l2++){
		if(l1==l2)continue;//同じ線分は結ばない
		for(int r1=0;r1<2;r1++){
			for(int r2=0;r2<2;r2++){
				len1=sqrt(pow(xs[r1][l1]-xs[r2][l2],2)+pow(ys[r1][l1]-ys[r2][l2],2));
				lensMemo[r1][r2][l1][l2]=len1;
			}
		}
	}
}
//スタート地点となる線分のリストを作る
std::priority_queue<State> pQ;
State s,nextS;
int ansPerm=0;
s.len=0;//長さ0
for(int i=0;i<n;i++){
	s.r=0;//どちらの両端から出発するか
	s.perm=(1<<i);//スタートの線分を使用禁止にする
	s.nowNo=i;//今いる線分
	pQ.push(s);
	s.r=1;//逆の端から出発する
	pQ.push(s);
	ansPerm|=(1<<i);//答えの組み合わせを立てておく
}
double ansLen=0;
for(int i=0;i<n;i++){
	ansLen+=sqrt(pow(xs[0][i]-xs[1][i],2)+pow(ys[0][i]-ys[1][i],2));
}	
while(!pQ.empty()){
	s=pQ.top();
	pQ.pop();
	if(s.perm==ansPerm)break;//答え到達
	len1=memo[s.r][s.nowNo][s.perm];
	if(first[s.r][s.nowNo][s.perm]==false&&len1<s.len)continue;//これより短い折れ線があった
	memo[s.r][s.nowNo][s.perm]=s.len;
	first[s.r][s.nowNo][s.perm]=false;
	for(int i=0;i<n;i++){
		if((s.perm&(1<<i))!=0)continue;//この線分は接続済み
		nextS.perm=(s.perm|(1<<i));
		nextS.nowNo=i;
		nextS.len=s.len+lensMemo[s.r][0][s.nowNo][i];//端点0と線分でつなげる
		nextS.r=1;//次は端点1からスタート
		len1=memo[nextS.r][nextS.nowNo][nextS.perm];
		if(first[nextS.r][nextS.nowNo][nextS.perm]==true||len1>nextS.len){//より短いルートか初めて
			memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
			first[nextS.r][nextS.nowNo][nextS.perm]=false;
			pQ.push(nextS);
		}
		nextS.len=s.len+lensMemo[s.r][1][s.nowNo][i];//端点1と線分でつなげる
		nextS.r=0;//次は端点0から出発
		len1=memo[nextS.r][nextS.nowNo][nextS.perm];
		if(first[nextS.r][nextS.nowNo][nextS.perm]==true||(len1>nextS.len)){//より短いルートか初めてだった
			memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
			first[nextS.r][nextS.nowNo][nextS.perm]=false;
			pQ.push(nextS);
		}
	}
}
printf("Case %d: %.5lf\n",i,s.len+ansLen);
}
int main(){
int n,i=1;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	setData(n,i);
	i++;
}
}