「AOJ Problem Set from ALDS1 問30～34」の編集履歴（バックアップ）一覧に戻る

AOJ Problem Set from ALDS1 問30～34 - (2014/01/23 (木) 21:15:52) のソース

*Graph I - Graph
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A
グラフのつながりを表示する問題。

 #include<stdio.h>
 #include<string.h>
 const int LIMIT=101;
 int g[LIMIT][LIMIT];
 
 
 int main(){
 	int n,u,k,v;
 	scanf("%d",&n);
 	memset(g,0,sizeof(g));
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&u,&k);
  		while(k--){
 			scanf("%d",&v);
 			g[u][v]=1;
 		}
 	}
 	for(int i=1;i<=n;i++){
 		for(int j=1;j<=n;j++){
 			if(j>1)printf(" ");
 			printf("%d",g[i][j]);
  		}
 		printf("\n");
 	}
 }


*Graph I - Depth First Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
グラフを探索した過程を出力する問題。
問題文の中の
深さ優先探索の過程において、訪問するための頂点（現在の頂点に隣接する頂点あるいは探索の始点）が複数ある場合は辞書式順序で選択する。
の一文に注意。

 #include<stdio.h>
 #include<string.h>
 
 const int LIMIT=101;
 int time=1;
 int g[LIMIT][LIMIT],d[LIMIT]={0},f[LIMIT]={0};
 int n;
  
 void search(int p){
 	if(d[p]>0)return ;
 	d[p]=time;
 	time++;
 	for(int i=1;i<=n;i++){
 		if(g[p][i]==1&&d[i]==0){
  			search(i);
 		}
 	}
 	f[p]=time;
 	time++;
 }
 
 int main(){
 	int u,k,v;
 	scanf("%d",&n);
 	memset(g,0,sizeof(g));
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&u,&k);
  		while(k--){
 			scanf("%d",&v);
 			g[u][v]=1;
 		}
 	}
 	for(int i=1;i<=n;i++){
 		search(i);
 	}
 	for(int i=1;i<=n;i++)printf("%d %d %d\n",i,d[i],f[i]);
 }


*Graph I - Breadth First Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C
グラフを幅優先探索する問題。


 #include<stdio.h>
 #include<string.h>
 #include<queue>
 
 const int LIMIT=101;
 int g[LIMIT][LIMIT],h[LIMIT];
  
 int main(){
 	int n,u,k,v;
 	scanf("%d",&n);
  	memset(g,0,sizeof(g));
 	memset(h,-1,sizeof(h));
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&u,&k);
 		while(k--){
 			scanf("%d",&v);
 			g[u][v]=1;
 		}
 	}
 	std::queue<int> qu;
  	qu.push(1);
 	h[1]=0;
	while(qu.empty()==false){
 		int p=qu.front();
 		qu.pop();
 		for(int i=1;i<=n;i++){
 			if(g[p][i]==1&&h[i]==-1){
 				h[i]=h[p]+1;
 				qu.push(i);
 			}
  		}
 	}
 	for(int i=1;i<=n;i++)printf("%d %d\n",i,h[i]);
 }




*Graph II - Minimum Spanning Tree
グラフの最小全域木の重みを求める問題。
何か効率が悪い方法を指定されていますが、指定の意図をくみ取って実装。

 #include<stdio.h>
 static const int MAX = 500;
 static const int INFTY = (1<<21);
 
 main(){
  int n, i, j, e, sum;
  int p[MAX],M[MAX][MAX];
 
  scanf("%d", &n);
  for ( i = 0; i< n; i++ ){
    p[i]=-1;
    for ( j = 0; j < n; j++ ){
      scanf("%d", &e);
      M[i][j] = (e==-1)?INFTY:e;
    }
  }
    for(int i=0;i<n;i++){
   	int p1,p2,g=INFTY;
 	for(int nowP=1;nowP<n;nowP++){
 		if(p[nowP]!=-1)continue;
  		for(int e=0;e<n;e++){
 			if(M[nowP][e]<g && (p[e]!=-1 || e==0)){
 				g=M[nowP][e];
 				p1=nowP;
 				p2=e;
 			}
  		}
 	}
 	p[p1]=p2;
  }
  sum = 0;
  
  for ( i = 0; i < n; i++ ){
    if ( p[i] != -1 ) sum += M[i][p[i]];
  }
   
   printf("%d\n", sum);
   
   return 0;
 }