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

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

AOJ1011~1020 - (2011/11/11 (金) 22:08:58) のソース

----
*1014 Computation of Minimum Length of Pipeline
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014
源泉から都市へパイプラインを引く問題。
都市間の距離、源泉から都市への距離が与えれるので最小の距離でパイプを接続せよという問題。

解法
どの源泉も供給能力は同じで区別がつきません。
源泉を全て丸で囲んで1点とみなし、源泉から都市への最小距離を最初に更新します。
後は都市と源泉を点とみなしグラフの上でプリム法で接続していくだけです。




 #include<stdio.h>
 #include<queue>
 #include<string.h>
 #include <algorithm>
 int map[102][102];//0が源泉ひとまとめ、1以降が都市
 struct Edge{
	int to,len;//エッジの接続先と繋げるパイプの長さ
	bool operator<(const Edge& e)const{
		return e.len<len;
	}
 };
 const int stop=0;
 int prim(int d){
	//プリム法でパイプラインの配置を解く。
	//まず源泉は全て長さ0の辺でつながっているという過程で始める
	std::priority_queue<Edge> qu;	
	bool conOKs[101];
	memset(conOKs,true,sizeof(conOKs));
	Edge edge;
	edge.len=0;
	edge.to=0;
	qu.push(edge);//最初長さ0で源泉に接続する
	int nextP,sumLen=0,count=0;//
	while(!qu.empty()){
		edge=qu.top();//一番短いパイプラインを選んでいく
		qu.pop();
		nextP=edge.to;
		
		if(conOKs[nextP]==false) continue;//接続済みの都市にパイプラインをつなげようとした
		conOKs[nextP]=false;
		count++;//つなげた都市の数
		sumLen+=edge.len;//答えの集計
		if(count==d+1) break;//全ての都市と源泉をつないだら終了	
		for(int i=0;i<=d;i++){
			if(conOKs[i]==false||map[nextP][i]==stop)continue;//もうパイプを通した都市もしくは接続不能の都市への接続は無視する
			edge.to =i;
			edge.len=map[nextP][i];
			qu.push(edge);
		}
	}
	return sumLen;
 }
 void setData(int s,int d){
	int temp;
	memset(map,stop,sizeof(map));
	for(int i=0;i<s;i++){
		for(int j=1;j<=d;j++){
			scanf("%d",&temp);
			if(map[0][j]==0 || (map[0][j]>temp&&temp!=stop)){
				map[0][j]=temp;//全ての源泉を丸で囲んで1点とみなす
			}
			map[j][0]=map[0][j];
		}
	}	
	for(int i=1;i<d;i++){
		for(int j=i+1;j<=d;j++){
			scanf("%d",&map[i][j]);//都市間の距離のセット
			map[j][i]=map[i][j];
		}
	}
	printf("%d\n",prim(d));
 }
 int main(){
	int s,d;
	while(1){
		scanf("%d %d",&s,&d);
		if(s==0 && d==0) break;
		setData(s,d);
	}
 }