[关闭]
@lychee123 2017-08-13T22:22:38.000000Z 字数 1675 阅读 1114

HDU-1869:六度分离(floyd(单源最短路,可处理负边,大数据容易超时))

图论


Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(),空间复杂度为O()。

例题题面链接

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. int i,j,k,n,m,edge[111][111],st,en,flag;
  6. void init()
  7. {
  8. for(i=0;i<n;i++)
  9. for(j=0;j<n;j++)
  10. {
  11. if(i==j)
  12. edge[i][j]=0;//自己到自己距离为0
  13. else
  14. edge[i][j]=0x3fffffff;
  15. }
  16. }
  17. void floyd()
  18. {
  19. for(i=0;i<n;i++)
  20. {
  21. for(j=0;j<n;j++)
  22. {
  23. for(k=0;k<n;k++)
  24. {
  25. if(edge[j][k]>edge[j][i]+edge[i][k])
  26. edge[j][k]=edge[j][i]+edge[i][k];
  27. }
  28. }
  29. }
  30. for(i=0;i<n;i++)
  31. for(j=0;j<n;j++)
  32. {
  33. if(edge[i][j]>7)
  34. flag=1;
  35. }
  36. if(flag==0)
  37. printf("Yes\n");
  38. else
  39. printf("No\n");
  40. }
  41. int main()
  42. {
  43. while(~scanf("%d%d",&n,&m))
  44. {
  45. init();
  46. flag=0;
  47. for(i=0;i<m;i++)//邻接矩阵存边
  48. {
  49. scanf("%d%d",&st,&en);
  50. if(st!=en&&edge[st][en]>1)
  51. edge[st][en]=edge[en][st]=1;
  52. }
  53. floyd();
  54. }
  55. return 0;
  56. }
  57. 模板代码
  58. #include<stdio.h>
  59. #include<string.h>
  60. #include<algorithm>
  61. using namespace std;
  62. int edge[101][101];
  63. #define INFF 1e9+7;
  64. int n,m;
  65. void init()//初始化
  66. {
  67. int i,j;
  68. for(i=1;i<=n;i++)
  69. for(j=1;j<=n;j++)
  70. if(i==j)//自己到自己初始化为0
  71. edge[i][j]=0;
  72. else
  73. edge[i][j]=INFF;
  74. }
  75. void floyd()
  76. {
  77. int i,j,k;
  78. for(i=1;i<=n;i++)
  79. for(j=1;j<=n;j++)
  80. for(k=1;k<=n;k++)
  81. if(edge[j][k]>edge[j][i]+edge[i][k])
  82. edge[j][k]=edge[j][i]+edge[i][k];
  83. for(i=1;i<=n;i++)
  84. for(j=i;j<=n;j++)
  85. printf("%d->%d=%d\n",i,j,edge[i][j]);
  86. }
  87. int main()
  88. {
  89. int st,en,len;
  90. while(scanf("%d %d",&n,&m)!=EOF)
  91. {
  92. init();
  93. while(m--)//邻接矩阵存边
  94. {
  95. scanf("%d %d %d",&st,&en,&len);
  96. if(st!=en&&edge[st][en]>len)//注意重边和自环
  97. edge[st][en]=edge[en][st]=len;
  98. }
  99. floyd();
  100. }
  101. return 0;
  102. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注