poj1486 - Sorting Slides

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

题目大意:一些幻灯片,有一些数字在幻灯片里面,看能不能一个数字对应一张幻灯片
第一行代表有几张幻灯片
给出这几张幻灯片的坐标

接着n行代表1-n个数字对应的坐标
然后要求你打印一个确定的使一个数字对应一张幻灯片
如果不能对应输出none
可以的话就按ABCD..这样顺序打印出来

 
解题思路：当然这是个二分图，不过用拓扑排序也可以解决，用二分做起来会比较麻烦一点

一个二分匹配，将幻灯片和数字相交就连一条边
一次二分匹配后的能够得到最大匹配，再将最大匹配得到的这些边每条删除后看能不能得到最大匹配
如果还能得到最大匹配，那这条边就不是必须要的，所以在选的时候不选这条边。
每次删除一条边后记得要还原

  1. /*
  2. hungary
  3. Memory 1252K
  4. Time     0MS
  5. */
  6. #include
  7. using namespace std;
  8. #define MAXV 500
  9.  
  10. int n,nedges;			//n为顶点数，nedges为要选的边数，如果为0就输出none
  11. int map[MAXV][MAXV];			//标记前个到后个有没有边，1为有边，0没边
  12. int use[MAXV];				//一个求最大匹配的标记数组
  13. int link[MAXV];				//表示i连着link[i]，表示匹配后的一条边
  14. int edgs[MAXV][2];			//把第一次的最大匹配存进去
  15. int discover[MAXV];			//代表这条边选不选
  16.  
  17. bool dfs(int x){
  18.     int i,j;    
  19.     for(i=1;i<=n;i++){
  20.         if (use[i]==0&&map[x][i]) {
  21.             use[i]=1; j=link[i]; link[i]=x;
  22.             if (j==-1||dfs(j)) {
  23.                 return true;
  24.             }
  25.             link[i]=j;
  26.         }       
  27.     }
  28.     return false;
  29. } 
  30.  
  31. int hungary(){
  32. 	int num=0;
  33.     int i,j;
  34. 	memset(link,-1,sizeof(link));
  35. 	for(i=1;i<=n;i++){
  36. 		for(j=1;j<=n;j++) use[j]=0;
  37. 		if (dfs(i)) num++;
  38. 	}
  39. 	return num;
  40. } 
  41.  
  42. int main(){
  43. 	int i,j,sum;
  44. 	int x,y;
  45. 	int xmin[MAXV],xmax[MAXV],ymin[MAXV],ymax[MAXV];
  46. 	sum=0;
  47.  
  48. 	while(scanf("%d",&n) && n){
  49. 		memset(map,0,sizeof(map));
  50. 		memset(discover,1,sizeof(discover));
  51.  
  52. 		for(i=1;i<=n;i++)
  53. 			scanf("%d %d %d %d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);
  54.  
  55. 		for(i=1;i<=n;i++){					//构图
  56. 			cin>>x>>y;
  57. 			for(j=1;j<=n;j++)
  58. 				if(x>=xmin[j] && x<=xmax[j] && y>=ymin[j] &&y<=ymax[j])
  59. 				map[i][j]=1;
  60. 		}
  61.  
  62. 		printf("Heap %d\n",++sum);
  63. 		if(hungary()==n){			//第一次匹配
  64. 			nedges=n;				//记录必须被匹配的边数
  65. 			for(i=1;i<=n;i++){		//把第一次匹配的边保存下来
  66. 				edgs[i][0]=i;			
  67. 				edgs[i][1]=link[i];
  68. 			}
  69. 			for(i=1;i<=n;i++){			//把每条边删除后再匹配
  70. 				map[ edgs[i][1] ][ edgs[i][0] ]=0;
  71. 				if(hungary()==n){			//找到的最大匹配数没变
  72. 					discover[i]=0;				//这条边不选
  73. 					nedges--;					//选的边数减小
  74. 					map[ edgs[i][1] ][ edgs[i][0] ]=1;		//还原
  75. 				}	
  76. 				else
  77. 					map[ edgs[i][1] ][ edgs[i][0] ]=1;	//还原
  78. 			}
  79. 		}
  80. 		else
  81. 			cout<<"none"<
  82.  
  83. 		if(nedges==0) cout<<"none"<//若所有的边都不选
  84. 		else{
  85. 			for(i=1;i<=n;i++)
  86. 				if(discover[i])	printf("(%c,%d) ",edgs[i][0]+'A'-1,edgs[i][1]);
  87. 			cout<
  88. 		}
  89. 		cout<
  90. 	}
  91. 	return 0;
  92. }


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

 

  1. /*
  2. topsort
  3. Memory 188K
  4. Time    0MS
  5. */
  6. #include
  7. using namespace std;	
  8.  
  9. int n;
  10. int pic[30][4],p[30][2];//用来输入保存
  11. int flag[60][60];		//一个图，相当于一个发现数组  
  12. int d[61];				//度
  13. int ans[61][2];			//保存字母对应的数字
  14.  
  15. int cmp(const void *i1,const void *i2) {
  16. 	return *((int *)i1)-*((int *)i2);
  17. }
  18.  
  19. void Input(){
  20. 	int i,j;
  21. 	for(i=1;i<=n;i++)
  22. 		scanf("%d%d%d%d",&pic[i][0],&pic[i][1],&pic[i][2],&pic[i][3]);
  23. 	for(i=1;i<=n;i++)
  24. 		scanf("%d%d",&p[i][0],&p[i][1]);
  25. 	
  26. 	memset(flag,0,sizeof(flag));
  27. 	memset(d,0,sizeof(d));  
  28. 	
  29. 	for(i=1;i<=n;i++)
  30. 		for(j=1;j<=n;j++)
  31. 			if (p[i][0]>pic[j][0] && p[i][0]1] && p[i][1]>pic[j][2] && p[i][1]3]){
  32. 				d[i+n]++;
  33. 				d[j]++;
  34. 				flag[i+n][j]=flag[j][i+n]=1;                                                                  
  35. 			}
  36. }
  37.  
  38. void Del(int p){
  39. 	for(int i=1;i<=2*n;i++)		//寻找相邻的点，使他们度减一
  40. 		if (flag[i][p]){
  41. 			d[i]--;
  42. 			flag[i][p]=flag[p][i]=0;			
  43. 		}
  44. 		d[p]=0;						//代表当前这点已经找完了
  45. } 
  46.  
  47. void topsort(){
  48. 	int i,j;
  49. 	int step;				//代表有多少个度为一的点
  50. 	for(step=1;step<=n;step++){
  51. 		for(i=1;i<=2*n;i++)		//找到度为一的点
  52. 			if(d[i]==1) break;
  53. 			if (i>2*n) break;		//没找到就退出
  54. 			if (i>n){
  55. 				for(j=1;j<=n;j++)
  56. 					if (flag[j][i]) break;
  57. 					Del(i);
  58. 					Del(j);	
  59. 					ans[step][0]=j;
  60. 					ans[step][1]=i-n;          
  61. 			}        
  62. 			else{
  63. 				for(j=n+1;j<=n+n;j++)
  64. 					if (flag[i][j]) break;    
  65. 					Del(i);
  66. 					Del(j);
  67. 					ans[step][0]=i;
  68. 					ans[step][1]=j-n;               
  69. 			}      
  70. 	}   
  71. 	
  72. 	if (step==1)				//从一开始就找不到度为一的点
  73. 		printf("none");
  74. 	else{
  75. 		qsort(ans+1,step-1,sizeof(ans[0]),cmp);	//因为输出是ABCD输出的，所以排序
  76. 		
  77. 		for(i=1;i
  78. 			printf("(%c,%d) ",'A'-1+ans[i][0],ans[i][1]);              
  79.     }
  80. 	printf("\n\n");    
  81. }
  82.  
  83. int main(){
  84. 	int test=0;
  85. 	while(scanf("%d",&n),n){
  86. 		printf("Heap %d\n",++test);
  87. 		Input();			//输入
  88. 		topsort();               //拓扑排序      
  89.     }
  90. 	return 0;  
  91. }


 

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

评论记录：

未查询到任何数据！