poj1161 - Walls

                                  想看更多的解题报告: http://iyenn.com/rec/1824570.html
                                  转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：给出n个点，在这些点中有些点是俱乐部点，并且有m个区域是由点围成的
输入第一行代表n个点
第二行代表m个区域
第3行代表俱乐部有L个
第四行有L个数，分别标记哪些个点事是俱乐部
接下来2*m行，代表m个区域，每个区域由两行表示，第一行为区域由T个点围成的，
第二行T个数代表是哪些点围成这个区域，这些点按逆时针围成这个区域，相邻两点代表一条边
最后一点和第一点也是一条边，这样就是一个闭合的区域

现在问，在图中找出一个区域，使得所有俱乐部点到这个区域所要穿过的边之和最少，
输出最少的边数之和

解题思路:先建图建错了，很尴尬的重新建图，将所有区域看成点建图，然后接下来的做法可以看代码注释
写完这题已经天黑了，被这题虐了一下午。...

  1. /*
  2. floyd
  3. Memory 788K
  4. Time   63MS 
  5. */
  6. #include 
  7. using namespace std;
  8. #define MAXE 205
  9. #define MAXV 255
  10. #define INF INT_MAX
  11. #define min(a,b) (a>b?b:a)
  12.  
  13. int n,m;
  14. int club[35],clubsum;						//俱乐部情况
  15. int regsum,firstv,secondv,tmpv,tmpedge;		                //用来处理区域	
  16. int map[MAXE][MAXE];						//首先保存区域相邻情况，然后保存最短路径
  17. int edge[MAXV][MAXV];						//看边在哪个区域，一条边只能是包含两个区域
  18. int markedge[MAXV][MAXE];					//markedge[i][j]标记i点与j区域是否相邻
  19. int ans;
  20.  
  21. void floyd(){
  22. 	int k,i,j;
  23. 	for(i=0;i0;			//这里注意初始化
  24.  
  25. 	for(k=0;k
  26. 		for(i=0;i
  27. 		if(map[i][k]!=-1){
  28. 			for(j=0;j
  29. 				if(map[k][j]!=-1){
  30. 					//如果i到j走不通，直接赋值
  31. 					if(map[i][j]==-1 || map[i][k]+map[k][j]
  32. 						map[i][j]=map[i][k]+map[k][j];
  33. 				}
  34. 		}
  35. }
  36.  
  37. int main(){
  38. #ifndef U
  39. 		freopen("d:\\test.in","r",stdin);
  40. #endif
  41. 	int i,j,k;
  42. 	int tmpv,tmpedge;
  43. 	while(~scanf("%d",&m)){
  44. 		scanf("%d%d",&n,&clubsum);
  45. 		for(i=0;iscanf("%d",&club[i]);
  46. 		
  47. 		memset(map,-1,sizeof(map));
  48. 		memset(markedge,0,sizeof(markedge));
  49. 		memset(edge,-1,sizeof(edge));
  50. 		for(i=0;i
  51. 			scanf("%d%d",®sum,&firstv);
  52. 			tmpv=firstv;
  53. 			markedge[firstv][i]=1;
  54. 			for(j=1;j
  55. 				scanf("%d",&secondv);
  56. 				markedge[secondv][i]=1;								//标记点和区域相邻
  57. 				tmpedge=edge[tmpv][secondv];
  58. 				if(tmpedge!=-1){									//一条边只被两个区域包含
  59. 						map[tmpedge][i]=map[i][tmpedge]=1;			//这两个区域相邻了
  60. 				}else{
  61. 					edge[tmpv][secondv]=edge[secondv][tmpv]=i;
  62. 				}
  63. 				
  64. 				tmpv=secondv;
  65. 			}
  66. 			tmpedge=edge[tmpv][firstv];
  67. 			if(tmpedge!=-1){
  68. 					map[tmpedge][i]=map[i][tmpedge]=1;
  69. 			}else{
  70. 				edge[tmpv][firstv]=edge[firstv][tmpv]=i;
  71. 			}
  72. 		}
  73. 		//得到相邻区域的图后求最短路径
  74. 		floyd();
  75. 	
  76. 		ans=INF;
  77. 		for(i=0;i
  78. 			int sum=0;
  79. 			for(j=0;j//找出和俱乐部点相邻的区域，在这些区域到i区域的一个最小值之和与答案比较
  80. 				tmpv=INF;
  81. 				for(k=0;k
  82. 					if(markedge[club[j]][k]){
  83. 						tmpv=min(tmpv,map[k][i]);
  84. 					}
  85. 				sum+=tmpv;
  86. 			}
  87. 			ans=min(ans,sum);
  88. 		}
  89. 		printf("%d\n",ans);
  90. 	}
  91. 	return 0;
  92. }


=================================================================

 

  1. /*
  2. 前面错误的代码留着做个纪念吧
  3. */
  4. #include 
  5. #include 
  6. using namespace std;
  7. #define MAXV 260
  8. #define MAXR 210
  9. #define INF INT_MAX
  10. #define min(a,b) (a>b?b:a)
  11.  
  12. int map[MAXV][MAXV];				//存边的连通情况
  13. int ans[MAXV][MAXR];				//存点到地区最少要穿过几条线
  14. int m,n;							//地区与点的总数
  15. int club[40],clubsum;				//俱乐部的情况
  16. int vsum[MAXR],ver[MAXR][MAXV];		//存地区情况
  17. int flag[MAXR];	//存边界情况,flag标记地区是否为边界地区
  18. int d[MAXV][MAXV];					//从点到其他点最少经过几条边
  19.  
  20. void bfs(int first){
  21. 	queue <int>q;
  22. 	bool vis[MAXV];
  23. 	int i,v;
  24. 	memset(vis,0,sizeof(vis));
  25.  
  26. 	q.push(first);
  27. 	vis[first]=1;
  28. 	while(!q.empty()){
  29. 		v=q.front();q.pop();
  30. 		for(i=1;i<=n;i++)
  31. 			if(!vis[i] && map[v][i]){
  32. 				q.push(i);
  33. 				vis[i]=1;
  34. 				d[first][i]=d[first][v]+1;
  35. 			}
  36. 	}
  37. }
  38.  
  39. int main(){
  40. #ifndef U
  41. //	freopen("d:\\test.in","r",stdin);
  42. #endif
  43. 	int i,j,k;
  44. 	int key,tmp,vtmp;
  45. 	while(~scanf("%d",&m)){
  46. 		scanf("%d%d",&n,&clubsum);
  47. 		for(i=0;iscanf("%d",&club[i]);	//输入俱乐部情况
  48.  
  49. 		tmp=-1;
  50. 		memset(map,0,sizeof(map));						//输入地区情况，并且连边
  51. 		for(i=0;i
  52. 			scanf("%d%d",&vsum[i],&ver[i][0]);
  53. 			for(j=1;j
  54. 				scanf("%d",&ver[i][j]);
  55. 				map[ver[i][j-1]][ver[i][j]]=map[ver[i][j]][ver[i][j-1]]=1;
  56. 			}
  57. 			map[ver[i][j-1]][ver[i][0]]=map[ver[i][0]][ver[i][j-1]]=1;
  58. 			if(vsum[i]>tmp){tmp=vsum[i];vtmp=i;}
  59. 		}
  60.  
  61. 		memset(flag,0,sizeof(flag));
  62. 		for(i=0;i
  63. 			for(j=0;j
  64. 			if(!flag[j]){
  65. 				for(k=0;k
  66. 					if(ver[vtmp][i]==ver[j][k]) break;
  67. 				}
  68. 				if(k1;
  69. 			}
  70. 		}
  71.  
  72. 		memset(d,0,sizeof(d));
  73. 		for(i=1;i<=n;i++) bfs(i);
  74. 		
  75. 		for(i=1;i<=n;i++){
  76. 			for(j=0;j
  77. 				ans[i][j]=d[i][ver[j][0]];
  78. 				for(k=1;k
  79. 					ans[i][j]=min(ans[i][j],d[i][ver[j][k]]);
  80. 				}
  81. 			}
  82. 		}
  83.  
  84. 		for(i=0;i
  85. 			for(j=0;j
  86. 				if(flag[j])
  87. 					ans[ver[vtmp][i]][j]=min(ans[ver[vtmp][i]][j],1);
  88. 		}
  89.  
  90. 		key=INF;
  91. 		for(i=0;i
  92. 			tmp=0;
  93. 			for(j=0;j
  94. 				tmp+=ans[club[j]][i];
  95. 			}
  96. 			key=min(key,tmp);
  97. 		}
  98. 		printf("%d\n",key);
  99. 	}
  100. 	return 0;
  101. }


 

注：本文转载自blog.csdn.net的wangjian8006的文章"http://blog.csdn.net/wangjian8006/article/details/7958838"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！