*Connect Line Segments http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2117 平面上に散らばってる線分を繋げて一本の長い折れ線を作るとき、最小の長さの折れ線を作った時の長さを答えよという問題。 プログラミングコンテストの過去問を1000問解いたって学歴、職歴、実績の三無い人間の私では世間から何の評価もされません。 プロコンの問題を解くことは私にとって単なる趣味でしかないのです。 使い捨て労働で仕事を探しながらこの趣味を完遂するのだけが楽しみです。 何かアプリでも作って売れたら世間からの評価も変わるかもしれないのでその可能性にかけるくらいです。 解法 さてこの問題自分なりに考えた解法は以下の通りです。 単純に深さ優先探索を行うと線分が11本を超えたあたりで11！となり計算量が限界に近づきます。 分岐が不可能なのでプリム法も使えません。 よって動的計画法を使わなくてはいけません。 動的計画法は、memo[次に線分を繋げる両端のどちらの点か][これから新しく線分を伸ばす線][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。 で動的計画法を適用していくだけの簡単な問題です。 この問題は私はあまりいい解法ではなかったようです。 私の場合スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。 この問題を解いた時点でカンニングして解いたプロコンの過去問題は480問中31問。 #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++; } }
