poj1466 - Girls and Boys

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

 

题目大意：有n个学生，每个学生都和一些人又关系，现在要你找出最大的人数，使得这些人之间没关系

解题思路：裸的最大独立集，最大独立集=点数-最大匹配数
这里注意因为是两两匹配，所以求出的匹配值要除上个2

优化了几下，时间不断减少

 

  1. /*
  2. Memory 1164K
  3. Time   3844MS
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 505
  8.  
  9. int map[MAXV][MAXV];
  10. int n;
  11. int link[MAXV],use[MAXV];
  12.  
  13. bool dfs(int x){
  14. 	int i,j;
  15. 	for(i=0;i
  16. 		if(!use[i] && map[x][i]){
  17. 			use[i]=1;
  18. 			if(link[i]==-1 || dfs(link[i])){
  19. 				link[i]=x;
  20. 				return true;
  21. 			}			
  22. 		}
  23. 	}
  24. 	return false;
  25. }
  26.  
  27. int hungary(){
  28. 	int num=0,i;
  29. 	memset(link,-1,sizeof(link));
  30. 	for(i=0;i
  31. 		memset(use,0,sizeof(use));
  32. 		if(dfs(i)) num++;
  33. 	}
  34. 	return n-num/2;
  35. }
  36.  
  37. int main(){
  38. 	int i,j,cnt;
  39. 	int a,b;
  40. 	while(~scanf("%d",&n)){
  41. 		memset(map,0,sizeof(map));
  42. 		for(i=0;i
  43. 			scanf("%d: (%d)",&a,&cnt);
  44. 			for(j=0;j
  45. 				scanf("%d",&b);
  46. 				map[a][b]=1;
  47. 			}
  48. 		}
  49. 		printf("%d\n",hungary());
  50. 	}
  51. 	return 0;
  52. }

 

 

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

 

 

  1. /*
  2. Memory  412K
  3. Time  1391MS
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 500
  8.  
  9. int vx[MAXV],vy[MAXV],n;
  10. bool map[MAXV][MAXV];
  11. bool use[MAXV];
  12.  
  13. bool dfs(int x){
  14. 	int i;
  15. 	for(i=0;i
  16. 		if(map[x][i] && !use[i]){
  17. 			use[i]=1;
  18. 			if(vy[i]==-1 || dfs(vy[i])){
  19. 				vy[i]=x;
  20. 				vx[x]=i;
  21. 				return true;
  22. 			}
  23. 		}
  24. 	}
  25. 	return false;
  26. }
  27.  
  28. int hungary(){
  29. 	int i,num=0,j;
  30. 	memset(vx,-1,sizeof(vx));
  31. 	memset(vy,-1,sizeof(vy));
  32. 	for(i=0;i
  33. 		if(vx[i]==-1){
  34. 			for(j=0;j0;
  35. 			if(dfs(i)) num++;
  36. 		}
  37. 	}
  38. 	return n-num/2;
  39. }
  40.  
  41. int main(){
  42. 	int i,j,cnt;
  43. 	int a,b;
  44. 	while(~scanf("%d",&n)){
  45. 		memset(map,0,sizeof(map));
  46. 		for(i=0;i
  47. 			scanf("%d: (%d)",&a,&cnt);
  48. 			for(j=0;j
  49. 				scanf("%d",&b);
  50. 				map[a][b]=1;
  51. 			}
  52. 		}
  53. 		printf("%d\n",hungary());
  54. 	}
  55. 	return 0;
  56. }



 

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

 

 

  1. /*
  2. Memory 188K
  3. Time  438MS
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 500
  8. #define MAXM 20000
  9.  
  10. typedef struct{
  11. 	int t,next;
  12. }Edge;
  13.  
  14. Edge edge[MAXM];
  15. int vx[MAXV],vy[MAXV],n,edge_sum;
  16. int headlist[MAXV];
  17. bool use[MAXV];
  18.  
  19. bool dfs(int x){
  20. 	int i,t;
  21. 	for(i=headlist[x];i!=-1;i=edge[i].next){
  22. 		t=edge[i].t;
  23. 		if(!use[t]){
  24. 			use[t]=1;
  25. 			if(vy[t]==-1 || dfs(vy[t])){
  26. 				vy[t]=x;
  27. 				vx[x]=t;
  28. 				return true;
  29. 			}
  30. 		}
  31. 	}
  32. 	return false;
  33. }
  34.  
  35. int hungary(){
  36. 	int i,num=0,j;
  37. 	memset(vx,-1,sizeof(vx));
  38. 	memset(vy,-1,sizeof(vy));
  39. 	for(i=0;i
  40. 		if(vx[i]==-1){
  41. 			for(j=0;j0;
  42. 			if(dfs(i)) num++;
  43. 		}
  44. 	}
  45. 	return n-num/2;
  46. }
  47.  
  48. void add(int a,int b){
  49. 	edge[edge_sum].t=b;
  50. 	edge[edge_sum].next=headlist[a];
  51. 	headlist[a]=edge_sum++;
  52. }
  53.  
  54. int main(){
  55. 	int i,j,cnt;
  56. 	int a,b;
  57. 	while(~scanf("%d",&n)){
  58. 		edge_sum=0;
  59. 		memset(headlist,-1,sizeof(headlist));
  60. 		for(i=0;i
  61. 			scanf("%d: (%d)",&a,&cnt);
  62. 			for(j=0;j
  63. 				scanf("%d",&b);
  64. 				add(a,b);
  65. 			}
  66. 		}
  67. 		printf("%d\n",hungary());
  68. 	}
  69. 	return 0;
  70. }


 

 

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

 

 

  1. /*
  2. Memory 184K
  3. Time  422MS
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 500
  8. #define MAXM 20000
  9.  
  10. typedef struct{
  11. 	int t,next;
  12. }Edge;
  13.  
  14. Edge edge[MAXM];
  15. int link[MAXV],n,edge_sum;
  16. int headlist[MAXV];
  17. bool use[MAXV];
  18.  
  19. bool dfs(int x){
  20. 	int i,t;
  21. 	for(i=headlist[x];i!=-1;i=edge[i].next){
  22. 		t=edge[i].t;
  23. 		if(!use[t]){
  24. 			use[t]=1;
  25. 			if(link[t]==-1 || dfs(link[t])){
  26. 				link[t]=x;
  27. 				return true;
  28. 			}			
  29. 		}
  30. 	}
  31. 	return false;
  32. }
  33.  
  34. int hungary(){
  35. 	int num=0,i;
  36. 	memset(link,-1,sizeof(link));
  37. 	for(i=0;i
  38. 		memset(use,0,sizeof(use));
  39. 		if(dfs(i)) num++;
  40. 	}
  41. 	return n-num/2;
  42. }
  43.  
  44. void add(int a,int b){
  45. 	edge[edge_sum].t=b;
  46. 	edge[edge_sum].next=headlist[a];
  47. 	headlist[a]=edge_sum++;
  48. }
  49.  
  50. int main(){
  51. 	int i,j,cnt;
  52. 	int a,b;
  53. 	while(~scanf("%d",&n)){
  54. 		edge_sum=0;
  55. 		memset(headlist,-1,sizeof(headlist));
  56. 		for(i=0;i
  57. 			scanf("%d: (%d)",&a,&cnt);
  58. 			for(j=0;j
  59. 				scanf("%d",&b);
  60. 				add(a,b);
  61. 			}
  62. 		}
  63. 		printf("%d\n",hungary());
  64. 	}
  65. 	return 0;
  66. }


 

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

评论记录：

未查询到任何数据！