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

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

AOJ1011~1020 - (2011/11/12 (土) 15:32:10) のソース

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







----
*1015 Dominating Set
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1015
最小の頂点支配集合を求める問題。

解法
初めはBitSetで解こうかと考えたのですが、最大頂点数が分からなかった(多分書いてない?)のでvectorに頂点支配されるかの状態を保存することにしました。
コードは深さ優先探索である点を頂点支配集合に入れる入れないを2分探索しているだけです。
素朴な方法で速度が出なかったので小手先のテクニックを入れたらコードが膨らみました。
深さ優先探索するまえに辺の多い点を優先して調べるよう並べ替えること、もう一つはある点で支配できる領域が他の点で支配できる領域のサブセットをなすならその点は探索で無視する。
ということをしています。
小手先すぎて駄目ですね、3倍しか速くなりませんでした。
頂点支配集合についてきちんと勉強することにしようと考えた問題でした。





  #include<stdio.h>
  #include<vector>
  #include <algorithm>
  #include <map>
  #include <set>
  struct vecSizeSorter
  {
    bool operator()( const std::vector<int>& lhs, const std::vector<int>& rhs ) const
    {
        return lhs.size() > rhs.size();
    }
  };
  //グローバル変数まとめ
  int ans,x;
  std::vector<std::vector<int> > map;//グラフのつながり
  std::vector<bool> subSet;//ある点で支配される領域が別の点のサブセットでないかのチェック
  //グローバル変数終わり
  void saiki(std::vector<bool> state,int p,int count,int vCount){
	if(ans<=vCount) return;
	//支配集合に入ってる数が全体になった
	if(count==x){
		ans=ans>vCount?vCount:ans;
		return;
	}
	if(p>=x)return;
	if(subSet[p]==true){
		saiki(state,p+1,count,vCount);
		return ;
	}
	int backCount=count;
	std::vector<bool> back=state;	
	//この点pを支配集合とする
	for(int i=0;i<map[p].size();i++){
		if(state[map[p][i]]==false){
			count++;
			state[map[p][i]]=true;
		}
	}
	if(backCount!=count){
		saiki(state,p+1,count,vCount+1);//支配集合とする
		state=back;//変化があったので元に戻す
		count=backCount;
	}
	saiki(state,p+1,count,vCount);//この点を支配集合としない
  }
  bool isSubSet(std::vector<int>& vec1,std::vector<int>& vec2){
	//ソート済みを渡すので必ずvec1>=vec2
	//vec2がvec1のサブセットでないかをチェックする
	std::set<int> sets;
	sets.insert(vec1.begin(),vec1.end());
	int count=sets.size();
	sets.insert(vec2.begin(),vec2.end());
	if(count==sets.size()){
		return true;
	}else{
		return false;
	}
  }
  void search(int x,int y){	
	std::vector<bool> state;
	ans=x+1;
	map.clear();
	map.resize(x);
	state.resize(x);
	int from,to;
	for(int i=0;i<y;i++){
		scanf("%d %d",&from,&to);
		map[from].push_back(to);
		map[to].push_back(from);
	}
	for(int i=0;i<x;i++){
		map[i].insert(map[i].begin(),i);//支配集合の中心となる点を先頭に挿入
		state[i]=false;
	}
	std::sort(map.begin(),map.end(),vecSizeSorter());//小手先テク頂点集合をソートして辺の多い点から検証する
	int p;
	std::map<int,int> temp;
	for(int i=0;i<x;i++){
		temp[map[i][0]]=i;//点の位置が入れ替わったので修正
	}
	for(int i=0;i<x;i++){
		for(int j=0;j<map[i].size();j++){
			map[i][j]=temp[map[i][j]];
		}
		std::sort(map[i].begin(),map[i].end());
	}
	subSet.clear();
	subSet.resize(x);//ある点で頂点支配できる点が他の点の頂点支配のサブセットなら無視する
	for(int i=0;i<x;i++)subSet[i]=false;
	for(int i=0;i<x-1;i++){
		for(int j=i+1;j<x;j++){
			if(isSubSet(map[i],map[j])==true){
				subSet[j]=true;
			}
		}
	}	
	//深さ優先探索で一つずつ点を頂点集合に含める含めないを試して最小値を求める
	saiki(state,0,0,0);
	printf("%d\n",ans);
  }
  int main(){
	int y;
	while(1){
		scanf("%d %d",&x,&y);
		if(x==0 && y==0) break;
		search(x,y);
	}
 }