poj1797 - Heavy Transportation

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

题目大意：有n个城市，m条道路，在每条道路上有一个承载量，现在要求从1到n城市最大承载量，而最大承载量就是从城市1到城市n所有通路上的最大承载量
解题思路：其实这个求最大边可以近似于求最短路，只要修改下找最短路更新的条件就可以了

 

  1. /*
  2. 4128K 375MS
  3. Dijkstra邻接矩阵
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 1010
  8. #define min(a,b) (a
  9.  
  10. int map[MAXV][MAXV],n,m;
  11.  
  12. int dijkstra(){
  13. 	int vis[MAXV],d[MAXV],i,j,v;
  14. 	for(i=1;i<=n;i++){
  15. 		vis[i]=0;
  16. 		d[i]=map[1][i];	//这个时候d不代表从1到n的最短路径，而是最大承载量
  17. 	}
  18. 	for(i=1;i<=n;i++){
  19. 		int f=-1;
  20. 		for(j=1;j<=n;j++)
  21. 			if(!vis[j] && d[j]>f){
  22. 				f=d[j];
  23. 				v=j;
  24. 			}
  25. 		vis[v]=1;
  26.  
  27. 		for(j=1;j<=n;j++)
  28. 			if(!vis[j] && d[j]<min(d[v],map[v][j])){
  29. 				d[j]=min(d[v],map[v][j]);
  30. 			}
  31. 	}
  32. 	return d[n];
  33. }
  34.  
  35. int main(){
  36. 	int t,i,j,sum,a,b,c;
  37. 	scanf("%d",&sum);
  38. 	for(t=1;t<=sum;t++){
  39. 		scanf("%d%d",&n,&m);
  40. 		for(i=0;i<=n;i++)
  41. 			for(j=0;j<=n;j++)
  42. 				map[i][j]=0;
  43. 		for(i=1;i<=m;i++){
  44. 			scanf("%d%d%d",&a,&b,&c);
  45. 			map[a][b]=map[b][a]=c;
  46. 		}
  47. 		printf("Scenario #%d:\n",t);
  48. 		printf("%d\n\n",dijkstra());
  49. 	}
  50. 	return 0;
  51. }


 

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

 

  1. /*
  2. spfa邻接矩阵
  3. 4156K 469MS 
  4. */
  5. #include 
  6. #include 
  7. using namespace std;
  8. #define MAXV 1010
  9. #define min(a,b) (a
  10.  
  11. int map[MAXV][MAXV],n,m;
  12.  
  13. int spfa(){
  14. 	queue <int>q;
  15. 	int i,j,v;
  16. 	int vis[MAXV],d[MAXV];
  17. 	for(i=1;i<=n;i++){
  18. 		vis[i]=0;
  19. 		d[i]=0;
  20. 	}
  21. 	q.push(1);
  22. 	vis[1]=1;
  23. 	while(!q.empty()){
  24. 		v=q.front();q.pop();
  25. 		vis[v]=0;
  26.  
  27. 		for(i=1;i<=n;i++){
  28. 			if(v==1 && map[v][i]){
  29. 				d[i]=map[v][i];
  30. 				q.push(i);
  31. 				vis[i]=1;
  32. 				continue;
  33. 			}
  34. 			if(d[i]<min(d[v],map[v][i])){
  35. 				d[i]=min(d[v],map[v][i]);
  36. 				if(!vis[i]){
  37. 					vis[i]=1;
  38. 					q.push(i);
  39. 				}
  40. 			}
  41. 		}
  42. 	}
  43. 	return d[n];
  44. }
  45.  
  46. int main(){
  47. 	int t,i,j,sum,a,b,c;
  48. 	scanf("%d",&sum);
  49. 	for(t=1;t<=sum;t++){
  50. 		scanf("%d%d",&n,&m);
  51. 		for(i=0;i<=n;i++)
  52. 			for(j=0;j<=n;j++)
  53. 				map[i][j]=0;
  54. 		for(i=1;i<=m;i++){
  55. 			scanf("%d%d%d",&a,&b,&c);
  56. 			map[a][b]=map[b][a]=c;
  57. 		}
  58. 		printf("Scenario #%d:\n",t);
  59. 		printf("%d\n\n",spfa());
  60. 	}
  61. 	return 0;
  62. }


 

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

 

  1. /*
  2. bellman-ford邻接矩阵
  3. Time Limit Exceeded
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 1010
  8. #define min(a,b) (a
  9.  
  10. int map[MAXV][MAXV],n,m;
  11.  
  12. int bellman_ford(){
  13. 	int i,j,v,k;
  14. 	int vis[MAXV],d[MAXV];
  15. 	for(i=1;i<=n;i++) d[i]=map[1][i];
  16.  
  17. 	for(i=1;i<=n;i++){
  18. 		for(j=1;j<=n;j++){
  19. 			for(k=1;k<=n;k++){
  20. 				if (d[k]<min(d[j],map[j][k]) && map[j][k])  d[k]=min(d[j],map[j][k]);
  21. 				if (d[j]<min(d[k],map[k][j]) && map[k][j])  d[j]=min(d[k],map[k][j]);
  22. 			}
  23. 		}
  24. 	}
  25. 	
  26. 	return d[n];
  27. }
  28.  
  29. int main(){
  30. 	int t,i,j,sum,a,b,c;
  31. 	scanf("%d",&sum);
  32. 	for(t=1;t<=sum;t++){
  33. 		scanf("%d%d",&n,&m);
  34. 		for(i=0;i<=n;i++)
  35. 			for(j=0;j<=n;j++)
  36. 				map[i][j]=0;
  37. 			for(i=1;i<=m;i++){
  38. 				scanf("%d%d%d",&a,&b,&c);
  39. 				map[a][b]=map[b][a]=c;
  40. 			}
  41. 			printf("Scenario #%d:\n",t);
  42. 			printf("%d\n\n",bellman_ford());
  43. 	}
  44. 	return 0;
  45. }


 

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

 

  1. /*
  2. 760K 1532MS
  3. bellman_ford邻接表
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 1010
  8. #define MAXE 1000010
  9. #define min(a,b) (a
  10.  
  11. struct {
  12. 	int s,e,w;
  13. }edge[MAXE];
  14.  
  15. int n,m;
  16.  
  17. int bellman_ford(){
  18. 	int i,j,d[MAXV];
  19. 	for(i=1;i<=n;i++) d[i]=0;
  20.  
  21. 	d[1]=0xffffff;
  22. 	
  23. 	for (i=1;i
  24. 		for (j=1;j<=m;j++){
  25. 			if (d[edge[j].e]<min(d[edge[j].s],edge[j].w))  d[edge[j].e]=min(d[edge[j].s],edge[j].w);
  26. 			if (d[edge[j].s]<min(d[edge[j].e],edge[j].w))  d[edge[j].s]=min(d[edge[j].e],edge[j].w);
  27. 		 }  
  28. 	}
  29. 	
  30. 	return d[n];
  31. }
  32.  
  33. int main(){
  34. 	int t,i,sum;
  35. 	scanf("%d",&sum);
  36. 	for(t=1;t<=sum;t++){
  37. 		scanf("%d%d",&n,&m);
  38. 		for(i=1;i<=m;i++){
  39. 			scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);
  40. 		}
  41. 		printf("Scenario #%d:\n",t);
  42. 		printf("%d\n\n",bellman_ford());
  43. 	}
  44. 	return 0;
  45. }


 

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

 

  1. /*
  2. 760K 250MS
  3. bell_ford邻接表优化
  4. */#include 
  5. using namespace std;
  6. #define MAXV 1010
  7. #define MAXE 1000010
  8. #define min(a,b) (a
  9.  
  10. struct {
  11. 	int s,e,w;
  12. }edge[MAXE];
  13.  
  14. int n,m;
  15.  
  16. int bellman_ford(){
  17. 	int i,j,d[MAXV];
  18. 	for(i=1;i<=n;i++) d[i]=0;
  19. 	
  20. 	d[1]=0xffffff;
  21. 	
  22. 	int flag=1;
  23. 	while(flag){
  24. 		flag=0;
  25. 		for (j=1;j<=m;j++){
  26. 			if (d[edge[j].e]<min(d[edge[j].s],edge[j].w))  {d[edge[j].e]=min(d[edge[j].s],edge[j].w);flag=1;}
  27. 			if (d[edge[j].s]<min(d[edge[j].e],edge[j].w))  {d[edge[j].s]=min(d[edge[j].e],edge[j].w);flag=1;}
  28. 		}  
  29. 	}
  30. 	
  31. 	return d[n];
  32. }
  33.  
  34. int main(){
  35. 	int t,i,sum;
  36. 	scanf("%d",&sum);
  37. 	for(t=1;t<=sum;t++){
  38. 		scanf("%d%d",&n,&m);
  39. 		for(i=1;i<=m;i++){
  40. 			scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);
  41. 		}
  42. 		printf("Scenario #%d:\n",t);
  43. 		printf("%d\n\n",bellman_ford());
  44. 	}
  45. 	return 0;
  46. }


 

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

 

  1. /*
  2. bellman-ford邻接矩阵优化
  3. 4124K 1485MS 
  4. */
  5. #include 
  6. using namespace std;
  7. #define MAXV 1010
  8. #define min(a,b) (a
  9.  
  10. int map[MAXV][MAXV],n,m;
  11.  
  12. int bellman_ford(){
  13. 	int i,j,v,k;
  14. 	int vis[MAXV],d[MAXV];
  15. 	for(i=1;i<=n;i++) d[i]=map[1][i];
  16. 	
  17. 	int flag=1;
  18. 	while(flag){
  19. 		flag=0;
  20. 		for(j=1;j<=n;j++){
  21. 			for(k=1;k<=n;k++){
  22. 				if (d[k]<min(d[j],map[j][k]) && map[j][k])  {d[k]=min(d[j],map[j][k]);flag=1;}
  23. 				if (d[j]<min(d[k],map[k][j]) && map[k][j])  {d[j]=min(d[k],map[k][j]);flag=1;}
  24. 			}
  25. 		}
  26. 	}
  27. 	
  28. 	return d[n];
  29. }
  30.  
  31. int main(){
  32. 	int t,i,j,sum,a,b,c;
  33. 	scanf("%d",&sum);
  34. 	for(t=1;t<=sum;t++){
  35. 		scanf("%d%d",&n,&m);
  36. 		for(i=0;i<=n;i++)
  37. 			for(j=0;j<=n;j++)
  38. 				map[i][j]=0;
  39. 			for(i=1;i<=m;i++){
  40. 				scanf("%d%d%d",&a,&b,&c);
  41. 				map[a][b]=map[b][a]=c;
  42. 			}
  43. 			printf("Scenario #%d:\n",t);
  44. 			printf("%d\n\n",bellman_ford());
  45. 	}
  46. 	return 0;
  47. }


 

 

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

评论记录：

未查询到任何数据！