AOJ171～180

0171　Dice Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171
サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。
サイコロの面にはアルファベットが書かれており、面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字である必要があります。
yとYやaとＡのような組み合わせのみ面を組み合わせることができます。
与えられたサイの情報から大きなさいころを組み立てられるか判別してください。

解法
良い解法思いつきませんでした。
さいを回転する関数を作り、さいころを回しては大きなさいころにサイを追加し深さ優先探索で全探索します。
探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。
もっと賢い解法もあると思うので調べてみるとよいでしょう。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ok=abs('A'-'a');
char xais[8][7];
char permXais[8][7];
bool allOK;
bool addOKs[8];
bool check(int deep){
int sa1,sa2,sa3;
if(allOK==true) return false;
if(deep==1){
	return abs(permXais[0][2]-permXais[1][3])==ok;
}else if(deep==2){
	return abs(permXais[0][4]-permXais[2][1])==ok;
}else if(deep==3){
	sa1=abs(permXais[1][4]-permXais[3][1]);
	sa2=abs(permXais[2][2]-permXais[3][3]);
	return (sa1==ok && sa2==ok);
}else if(deep==4){
	return abs(permXais[4][5]-permXais[0][0])==ok;
}else if(deep==5){
	sa1=abs(permXais[5][5]-permXais[1][0]);
	sa2=abs(permXais[5][3]-permXais[4][2]);
	return (sa1==ok && sa2==ok);
}else if(deep==6){
	sa1=abs(permXais[6][5]-permXais[2][0]);
	sa2=abs(permXais[6][1]-permXais[4][4]);
	return (sa1==ok && sa2==ok);
}else if(deep==7){
	sa1=abs(permXais[7][5]-permXais[3][0]);
	sa2=abs(permXais[7][1]-permXais[5][4]);
	sa3=abs(permXais[7][3]-permXais[6][2]);
	return (sa1==ok && sa2==ok && sa3==ok);
}
return true;
}
bool flatRound(char* xai,int deep){
char t=xai[2];
xai[2]=xai[1];
xai[1]=xai[3];
xai[3]=xai[4];
xai[4]=t;
return check(deep);
}
bool northRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[1];
xai[1]=xai[5];
xai[5]=xai[4];
xai[4]=t;
return check(deep);
}
bool eastRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[3];
xai[3]=xai[5];
xai[5]=xai[2];
xai[2]=t;
return check(deep);
}
void saiki(int deep){
if(deep==8){
	allOK=true;
	return;
}
   char temp[7];
   for(int k=0;k<8;k++){
       if(addOKs[k]==true){
       addOKs[k]=false;
       memcpy(&permXais[deep],&xais[k],7);
    for(int i=0;i<4;i++){
	    for(int j=0;j<4;j++){
		    if(flatRound(permXais[deep],deep))saiki(deep+1);
               if(allOK==true) return;
           }
	    northRound(permXais[deep],deep);
       }
    eastRound(permXais[deep],deep);
    for(int i=0;i<4;i++){
	    if(flatRound(permXais[deep],deep))saiki(deep+1);
           if(allOK==true) return;
       }
    for(int i=0;i<2;i++){
	    northRound(permXais[deep],deep);
    }
    for(int i=0;i<4;i++){
	    if(flatRound(permXais[deep],deep))saiki(deep+1);
           if(allOK==true) return;
       }
       addOKs[k]=true;
       }
   }
}
bool setData(){
scanf("%s",&xais[0]);
if(xais[0][0]=='0') return false;
memset(addOKs,true,8);
   for(int i=1;i<8;i++){
	scanf("%s",&xais[i]);
}
allOK=false;
saiki(0);
printf("%s\n",allOK?"YES":"NO");
return true;
}
int main(){
while(setData()==true){
}
}

0172　Doctor's Research Rooms

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0172
暗闇恐怖症の博士が各部屋に設けられたスイッチを操作しながら部屋から脱出する問題。

解法
この問題はメモ化による枝刈と優先順位付きキューによる幅優先探索を使って解きます。
探索中は、常に過去に通った部屋のスイッチを覚えながら進み、暗闇の部屋についたら過去にその部屋のスイッチをつけたことにして進みます。
ある部屋に入った時その部屋のスイッチを消すことのできるスイッチがあれば,記憶したスイッチのリストから削除します。
こうやって作業のターン数を数えながら進み、出口で全部の明りのついた部屋のスイッチを消せることを発見すれば探索の終了。
後は移動経路からスイッチのオンオフを復元していくだけです。
速度的にも上位だしサイズ的にもコンパクト結構いいコードができました。

#include<stdio.h>
#include<map>
#include<queue>
#include<vector>
#include<string.h>
#include<bitset>
struct state{
int lightState;//灯りのついてる消えてるのリストできるだけ消しておく
int onOffList;//過去にさかのぼって操作できるスイッチのリスト
int nowRoom;//今の部屋
int turn;//ターン数
std::vector<char> moveLog;//移動記録
int roomInCounts[16];//部屋に入った回数
};
class turnSorter {
public:
bool operator()(const state& l, const state& r) const {
	return l.turn>r.turn;
 	}
};
class stateSorter{
public:
bool operator()(const state& l,const state& r)const{
	if(l.lightState!=r.lightState)return l.lightState<r.lightState;
	if(l.onOffList !=r.onOffList )return l.onOffList <r.onOffList;
	return l.nowRoom<r.nowRoom;
}
};
void setData(int n,int m){
int con[20][20];
memset(con,0,sizeof(con));
int a,b;
for(int i=0;i<m;i++){
	scanf("%d %d",&a,&b);
	con[a][b]=con[b][a]=1;
}
state s,nextS;
s.lightState=0;
s.onOffList =0;
s.turn=0;
s.nowRoom=1;
memset(s.roomInCounts,0,sizeof(s.roomInCounts));
for(int i=0;i<n;i++){
	scanf("%d",&a);
	s.lightState|=(a==0?0:(1<<i));
}
int firstLightSet=s.lightState;
int switchs[20];
memset(switchs,0,sizeof(switchs));
//printf("?");
for(int i=1;i<=n;i++){
	scanf("%d",&a);
	while(a--){
		scanf("%d",&b);
		if(i==b)continue;//自分のいる部屋は消せない
		switchs[i]|=(1<<(b-1));
	}
}
s.onOffList=switchs[1]; 
s.roomInCounts[1]=1;
s.moveLog.push_back(1);
std::map<state,int,stateSorter> memo;
std::priority_queue<state,std::vector<state>,turnSorter> pQ;
memo[s]=0;
pQ.push(s);
int goal = 1<<(n-1);
int t1,t2;
std::bitset<20> lastBit;
bool goalOK=false;	
while(pQ.empty()==false){
	s=pQ.top();
	pQ.pop();
	if(s.nowRoom==n)goalOK=true;
	
	if(s.lightState==goal&& s.nowRoom==n){
		//ゴール状態に到達
		break;
	}
	if(s.nowRoom==n && ((s.lightState&(s.onOffList+goal))==s.lightState)){
		//全消しできることが判明
		lastBit=(s.lightState);//明りのついてる部屋を全て消す
		s.turn+=lastBit.count()-1;//最後の部屋以外消す
		s.lightState=goal;
		if(memo.find(s)==memo.end()||memo[s]>s.turn){
			memo[s]=s.turn;
			pQ.push(s);
		}
		continue;
	}
	for(int i=1;i<=n;i++){
		if(con[s.nowRoom][i]==1){
			t1=1<<(i-1);
			t2=~t1;//ビット反転
			nextS=s;				
			if((nextS.lightState&t1)==0){
				//明りのついてない部屋に入った
				if((nextS.onOffList&t1)==0)continue;//過去に通った部屋にこの部屋のスイッチがなかった
				nextS.turn+=2;//過去に明りをつけていたことにして２手消費
				nextS.lightState|=t1;//この部屋の明かりをつけた
			}else{
				nextS.turn++;//単なる移動
			}
			nextS.nowRoom=i;
			nextS.onOffList&=t2;//この部屋に入ったからもう過去において消したことにできない
			//過去に同じ状態を探索してないかのチェック
			if(memo.find(nextS)==memo.end()||memo[nextS]>nextS.turn){
				nextS.moveLog.push_back(i);//この部屋に移動したことを記録した
				nextS.roomInCounts[i]++;
				nextS.onOffList|=switchs[i];//この部屋のスイッチを操作リストに入れる 
				memo[nextS]=nextS.turn;
				pQ.push(nextS);//
			}
		}
	}
}
//とりあえず手数が正しいかのチェック
//printf("<%d %d>\n",s.turn,s.lightState);
if(s.lightState==goal){
	//ゴールにたどり着けたので出力処理を行う
	printf("You can go home in %d steps.\n",s.turn);
	s.lightState=firstLightSet;
	s.onOffList =switchs[1];
	for(int i=0;i<s.moveLog.size();i++){
		//明りをつける消す作業
		int rNo=s.moveLog[i];
		if(i>0)printf("Move to room %d.\n",rNo);
		for(int j=1;j<=n;j++){
			t1=(1<<(j-1));
			t2=~t1;
			if((switchs[rNo]&t1)!=0){
				//この部屋に部屋ｊのスイッチがあった
				if(s.roomInCounts[j]>0&&(s.lightState&t1)==0){
					//将来入る予定の部屋のスイッチが切れていたのでスイッチつける
					s.lightState|=t1;
					printf("Switch on room %d.\n",j);
				}
				if(s.roomInCounts[j]==0&&(s.lightState&t1)!=0){
					//もう入らない部屋のスイッチが付いていた
					s.lightState&=t2;//スイッチを消した
					printf("Switch off room %d.\n",j);
				}
			}
		}
		//この部屋を訪れた回数を一回減らす			
		s.onOffList|=switchs[rNo];
		s.roomInCounts[rNo]--;
	}
}else if(goalOK==true){
	printf("You can not switch off all lights.\n");
}else {
	printf("Help me!\n");
}

}
int main(){
int n,m;
while(1){
	scanf("%d %d",&n,&m);
	if(n==0&&m==0)break;
	setData(n,m);
}
}

0173　Haunted House

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0173
午前と午後のお化け屋敷の入場者数から総入場者数と売り上げを出力せよという問題。
解法
簡単な問題なのでただ書くだけです。
午前と午後の違いに注意するくらいです。

#include<stdio.h>
int main(){
char name[16];
int m,n;
while(scanf("%s %d %d",name,&m,&n)!=EOF){
	printf("%s %d %d\n",name,n+m,n*300+m*200);
}
}

0174 Badminton

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0174
バトミントンのサーブ記録から試合の得点を求めよという問題です。

解法
データの条件を試合終了時必ず2点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。
それが分かれば後はサーブ記録から互いに１点ずつ計算するだけです。

#include<stdio.h>
bool calc(){
char serve[101];
int score[2],p;
for(int i=0;i<3;i++){
	scanf("%s",serve);
	if(serve[0]=='0') return false;
	p=1;
	score[0]=score[1]=0;
	while(serve[p]!='\0'){
		score[serve[p]-'A']++;
		p++;
	}
	score[score[0]>score[1]?0:1]++;
	printf("%d %d\n",score[0],score[1]);
}
return true;
}
int main(){
while(calc()){
}
}

0175　A King in Hawaii

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0175
１０進数を４進数に変換せよという問題。
解法
m進数を表現する時はｍの余りを取りｍで割ってそれを文字列として保存して逆順に出力すれば何進数への変換であっても普遍的に計算できます。

#include<stdio.h>
int main(){
int n,p;
char ans[20];
while(1){
	scanf("%d",&n);
	if(n==-1) break;
	p=0;
	if(n==0){
		ans[0]='0';
		p++;
	}
	while(n>0){
		ans[p]=n%4+'0';
		n/=4;
		p++;
	}
	for(int i=p-1;i>=0;i--){
		printf("%c",ans[i]);
	}
	printf("\n");
}
}

0176 What Color?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0176
カラー表が与えられます。
色データがＲＧＢで与えられるので、カラー表の中でその色に最も近い色返すという問題。
解法
書いてある通りに上から実装します。
問題分の指定ではｓｑｒｔを使っていますが重要なのは色の距離だけなので、距離を２乗のまま扱うと計算が楽になります。

#include<stdio.h>
struct color{
	int r,g,b;
};
double colorLen2(color c1,color c2){
return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b);
}
int main(){
color colors[8]={ {0,0,0},{0,0,255},{0,255,0},{0,255,255}
			,{255,0,0},	{255,0,255},{255,255,0},{255,255,255}};
char colorNames[8][8]={"black","blue","lime","aqua", "red","fuchsia","yellow","white"};
color c;
char top;
int ans,len,tempLen;
while(1){
	scanf("%c",&top);
	if(top=='0') break;
	scanf("%2x%2x%2x%c",&c.r,&c.g,&c.b,&top);
	ans=0;
	len=colorLen2(c,colors[0]);
	for(int i=1;i<8;i++){
		tempLen=colorLen2(c,colors[i]);
		if(len>tempLen){
			len=tempLen;
			ans=i;
		}
	}
	printf("%s\n",colorNames[ans]);
}
}

0177 Distance Between Two Cities

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0177
地球上の２地点の緯度経度が与えられるので、その２地点間の距離を求めよという問題。

解法
はじめはベクトルと回転行列とcosの逆関数を使って求めました。
これでも十分な解法でしたが。
http://d.hatena.ne.jp/eha_s/20101007/1286464116
↑こちらのページに球面幾何の概念を使った解法が掲載されていました。
ベクトルを使うものより洗練された方法ですので、これを参考にコードを書き直しました。

#include<stdio.h>
#include<math.h>
int main(){
double a,b,c,d;
double cosC,ans;
while(1){
	scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
	if(a==-1 && b==-1 && c==-1 && d==-1) break;
	a=(90.0-a)/180.0*M_PI;
	c=(90.0-c)/180.0*M_PI;
	cosC =cos((d-b)/180.0*M_PI);
	ans=acos(cos(a)*cos(c)+sin(a)*sin(c)*cosC);
	printf("%d\n",(int)(ans*6378.1+0.5));
}
}

0178 TETORIS

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0178
簡易テトリスをシミュレートする問題。
解法
一段ずつint型で表現してbit演算で計算します。
イテレータを上手く使って計算量を落としたつもりです。

#include<stdio.h>
#include<vector>
void calc(int n){
std::vector<int> v;
std::vector<int>::iterator it;
v.push_back(63);
int d,p,q;
int blockYoko[]={0,16,24,28,30,31},yoko,tate;
for(int i=0;i<n;i++){
	scanf("%d %d %d",&d,&p,&q);
	if(d==1){
		yoko=blockYoko[p]>>(q-1);
		it=v.end();
		do{
			it--;
			if(((*it)&yoko)>0){
				it++;
				if(it==v.end()){
					v.push_back(yoko);
					it=v.end();
					it--;
				}else{
					(*it)|=yoko;
				}
				if((*it)==31){
					v.erase(it);
				}
                   break;
			}
		}while(it!=v.begin());
	}else{
		tate=16>>(q-1);
		it=v.end();
		do{
			it--;
			if(((*it)&tate)>0){
				it++;
				for(int j=0;j<p;j++){
					if(it==v.end()){
						v.push_back(tate);
						it=v.end();
					}else{
						(*it)|=tate;
						it++;
					}
				}
				it--;
				for(int j=0;j<p;j++){
					if((*it)==31){
						it=v.erase(it);
					}
					it--;
				}
				break;
			}
		}while(it!=v.begin());
	}
}
int sum=0,t;
for(unsigned int i=1;i<v.size();i++){
	t=v[i];
	sum+=(t&1)+((t>>1)&1)+((t>>2)&1)+((t>>3)&1)+((t>>4)&1);
}
printf("%d\n",sum);
}
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0) break;
	calc(n);
}
}

0179 Mysterious Worm

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0179
一定のルールの下時間とともに体の各部分の体色を変化させていく虫がいます。
この虫が体色を変化させていく時同じ色に落ち着くまでのターン数を答えるという問題です。

解法
シミュレートして、虫の体色変化を幅優先探索で追いかけるだけで簡単に解決できます。
この問題を正答した人たちのデータを見ると、コードの実行速度やコードサイズ、メモリ使用量が人によって違うので色々な解法があるのかもしれません。
調べてみるとよいでしょう。

#include<stdio.h>
#include<queue>
#include<string.h>
#include<set>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm w)const{
	for(int i=0;i<10;i++){
		if(body[i]!=w.body[i]) return body[i]<w.body[i];
	}
	return false;
}
};
bool allOK(char body[11]){
char color=body[0];
int p=1;
while(body[p]!='\0'){
	if(color!=body[p]) return false;
	p++;
}
return true;
}
char changeColor(char t1,char t2){
char ans[3][4]={".bg","b.r","gr."};
int x,y;
if(t1=='r')x=0;
if(t1=='g')x=1;
if(t1=='b')x=2;
if(t2=='r')y=0;
if(t2=='g')y=1;
if(t2=='b')y=2;
return ans[y][x];
}
void calc(char wormBody[11]){
std::queue<Worm> worms;
std::set<Worm> memo;
Worm w,nextW;
memcpy(w.body,wormBody,11);
w.turn=0;
worms.push(w);
memo.insert(w);
int wormSize=strlen(wormBody);
char color;	
while(!worms.empty()){
	w=worms.front();
	nextW=worms.front();
	if(allOK(w.body)){
		printf("%d\n",w.turn);
		return;
	}
	nextW.turn++;
	worms.pop();
	for(int i=0;i<wormSize-1;i++){
		if(w.body[i]!=w.body[i+1]){
			color=changeColor(w.body[i],w.body[i+1]);
			nextW.body[i]=nextW.body[i+1]=color;
			if(memo.find(nextW)==memo.end()){
				memo.insert(nextW);
				worms.push(nextW);
			}
			nextW.body[i]=w.body[i];
			nextW.body[i+1]=w.body[i+1];
		}
	}
}
printf("NA\n");
}
int main(){
char wormBody[11];
while(1){
	scanf("%s",wormBody);
	if(wormBody[0]=='0') break;
	calc(wormBody);
}
}

0179の少し賢い解法。
少し賢い方法として、色のそろった状態から初めて逆算して到達できる色のバラケタ状態を全て求めてターン数をメモ化しておきます。
全部生成できたら後はメモを参照するだけです。
このコードでも、これより早いコードを書いている方がいらっしゃるのでもっと賢い方法があるようです。

より賢い方法の予測
r,g,bを2bitで符号化します。
体は１０部位に分かれているので20bit必要です。
int型で虫の体を管理しＢｉｔ演算で虫の体色変化を計算するとよいでしょう。
アルゴリズムそのものを考え直すのが一番ですが、Ｂｉｔ演算で十分高速化できると考えます。
小手先の高速化テクニックですがＢｉｔ演算は有効です。

最も賢い方法の予測
体色から何回の色変更で色がそろうか、探索することなく計算だけで求める関数のようなものを用意できれば最高ですが、この問題はＮＰ困難な可能性が高いのでそのような式は立てれないのではと考えます。
あるルールに従えば自動的に最短手順で色をそろえられる。
そんなルールを探す方が賢そうです。

以下少し賢い方法のコード。

#include<stdio.h>
#include<queue>
#include<string.h>
#include<map>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm& w)const{
	return strcmp(w.body,body)>0?true:false;
}
};
void createWorm(char* body,char color,int size){
for(int i=0;i<11;i++){
	body[i]=i>=size?'\0':color;
}
}
std::map<Worm,int> memo;
void setWorm(){
std::queue<Worm> worms;
Worm w;
char *colors="rgb";
char color,c1,c2;
for(int wormSize=10;wormSize>1;wormSize--){
	w.turn=0;
	for(int i=0;i<3;i++){
		createWorm(w.body,colors[i],wormSize);
		memo[w]=0;
		worms.push(w);
	}
	while(!worms.empty()){
		w=worms.front();
		worms.pop();
		w.turn++;
		for(int i=0;i<wormSize-1;i++){
			if(w.body[i]==w.body[i+1]){
				color=w.body[i];
				if(color=='r'){
					c1='g';
					c2='b';
				}else if(color=='g'){
					c1='r';
					c2='b';
				}else{
					c1='r';
					c2='g';
				}
				w.body[i]=c1;
				w.body[i+1]=c2;
				if(memo.find(w)==memo.end()){
					worms.push(w);
					memo[w]=w.turn;
				}
				w.body[i]=c2;
				w.body[i+1]=c1;
				if(memo.find(w)==memo.end()){
					worms.push(w);
					memo[w]=w.turn;
				}
				w.body[i]=w.body[i+1]=color;
			}
		}
	}
}
}
int main(){
setWorm();
Worm w;
while(1){
	scanf("%s",w.body);
	if(w.body[0]=='0') break;
	if(memo.find(w)==memo.end()){
		printf("NA\n");
	}else{
		printf("%d\n",memo[w]);
	}
}
}

0179のＢｉｔ演算を使った解法です。
Ｂｉｔ演算は苦手なので分かりやすいコードで書いてみました。
上のコードをＢｉｔ演算に置き換えただけです。
これでも6倍速くなっただけであまり速度が出ていません。
Mapにintでなく構造体を使ったのが悪いのかもしれません。

#include<stdio.h>
#include<queue>
#include<map>
struct Worm{
int body;//ワームの体色を２bitずつ20bitで管理するｒ＝1、ｇ＝２、ｂ＝３
int turn;
bool operator<(const Worm& w)const{
	return body<w.body;
}
};
void createWorm(int& body,int color,int size){
body=0;
for(int i=0;i<size;i++){
	body|=(color<<(i<<1));
}
}
int wormHush(char body[11]){
int p=0,ans=0;
while(body[p]!='\0'){
	if(body[p]=='r'){
		ans|=(1<<(p<<1));
	}else if(body[p]=='g'){
		ans|=(2<<(p<<1));
	}else{
		ans|=(3<<(p<<1));
	}
	p++;
}
return ans;
}
std::map<Worm,int> memo;
void setWorm(){
std::queue<Worm> worms;
Worm w;
int rr=5,rg=9,rb=13,gr=6,gg=10,gb=14,br=7,bg=11,bb=15;
int mask=15,nowData;
int t,p,s,t1,t2;
for(int wormSize=10;wormSize>1;wormSize--){
	w.turn=0;
	for(int i=0;i<3;i++){
		createWorm(w.body,i+1,wormSize);
		memo[w]=0;
		worms.push(w);
	}
	while(!worms.empty()){
		w=worms.front();
		worms.pop();
		w.turn++;
		for(int i=0;i<wormSize-1;i++){
			p=i<<1;
			t=w.body;
			s=(t>>p)&mask;
			nowData=(~(mask<<p))&t;
			if(s==rr){
				t1=nowData|(gb<<p);
				t2=nowData|(bg<<p);	
			}else if(s==gg){
				t1=nowData|(rb<<p);
				t2=nowData|(br<<p);
			}else if(s==bb){
				t1=nowData|(rg<<p);
				t2=nowData|(gr<<p);
			}else{
				continue;
			}
			w.body=t1;
			if(memo.find(w)==memo.end()){
				memo[w]=w.turn;
				worms.push(w);
			}
			w.body=t2;
			if(memo.find(w)==memo.end()){
				memo[w]=w.turn;
				worms.push(w);
			}
			w.body=t;
		}
	}
}
}
int main(){
setWorm();
Worm w;
char body[11];
while(1){
	scanf("%s",body);
	if(body[0]=='0') break;
	w.body=wormHush(body);
	if(memo.find(w)==memo.end()){
		printf("NA\n");
	}else{
		printf("%d\n",memo[w]);
	}
}
}

0180　Stellar Performance of the Debunkey Family

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0180
島国で島を結ぶ橋が多すぎコストが高いので、いらない橋をこわして財政を立て直す問題。
全ての島をつなげつつ橋の維持費が最小になる、つまり最小全域木になるように橋を壊さなくてはなりません。

解法
プリム法で解きます。
0072　Carden Lanternを少しだけ簡単にした問題なので、コードをそのまま流用しました。

#include<stdio.h>
#include<queue>
#include<vector>
struct load{
int p1,p2,cost;
bool operator<(const load l)const{
return cost>l.cost;
}
};
void setMap(int n,int m){
int points[101]={0};
std::priority_queue<load> loads;
std::vector<load> map[101];
std::vector<load>::iterator it,end;
load l,start;
start.cost=2000000000; 
for(int i=0;i<m;i++){
scanf("%d %d %d",&l.p1,&l.p2,&l.cost);
map[l.p1].push_back(l);
map[l.p2].push_back(l);
start=l.cost<start.cost?l:start;
}
int count=1,ans=0,addOK;
loads.push(start);
while(n>count && loads.empty()==false){
l=loads.top();
loads.pop();
addOK=false;
if(points[l.p1]==0){
	addOK=true;
	points[l.p1]=1;
	it=map[l.p1].begin();
	end=map[l.p1].end();
	while(it!=end){
		loads.push(*it);
		it++;
	}
}
if(points[l.p2]==0){
	addOK=true;
	points[l.p2]=1;
	it=map[l.p2].begin();
	end=map[l.p2].end();
	while(it!=end){
		loads.push(*it);
		it++;
	}
}
if(addOK==true){
	count++;
	ans+=l.cost;
}
}
printf("%d\n",ans);
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0) break;
setMap(n,m);;
}
}

タグ：

+ タグ編集

「AOJ171～180」をウィキ内検索

最終更新：2012年07月11日 19:39

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0171　Dice Puzzle

0172　Doctor's Research Rooms

0173　Haunted House

0174 Badminton

0175　A King in Hawaii

0176 What Color?

0177 Distance Between Two Cities

0178 TETORIS

0179 Mysterious Worm

0180　Stellar Performance of the Debunkey Family

c21coterie @ ウィキ

AOJ171～180

更新履歴

メニュー

リンク

他のサービス

0171 Dice Puzzle

0172 Doctor's Research Rooms

0173 Haunted House

0174 Badminton

0175 A King in Hawaii

0176 What Color?

0177 Distance Between Two Cities

0178 TETORIS

0179 Mysterious Worm

0180 Stellar Performance of the Debunkey Family

0171　Dice Puzzle

0172　Doctor's Research Rooms

0173　Haunted House

0175　A King in Hawaii

0180　Stellar Performance of the Debunkey Family