题解与讨论区 1090: 网线布置

题解与讨论区 1090: 网线布置

[命题人 : ]
时间限制 : 5.000 sec  内存限制 : 512 MB

返回问题页面

题目描述

在新格尔软件公司,有N台电脑,编号为1N。现在只有1号电脑接入了网络,如果想让所有的电脑都接入网络,每台电脑可以特殊作为交换机(数据经过交换机处理不需要花费时间),就需要再连接一些网线(你可以认为网线能够提供的带宽无限大)。

可以把办公室想象成一个二维平面,每台电脑就是其中的一个点,如果两台电脑之间需要连接网线,那么网线从长度为min(|x1-x2,| , |y1-y2|  )

因为某种原因,需要1号电脑向每台电脑传输数据。现在求出1号电脑到其他所有电脑的最小时延之和。

现在,办公室主任菜怒文接到了这个任务,他希望你能帮帮他们算出这个最小值。

第1090题的题解

50块好兄弟

六花 的题解


本题是求1到所有点的最短路
可以发现,有意义的边只有四个方向与他最近的距离的点有一条边,然后dij就好

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<queue>
  4. #define INF 1e9
  5. #define NUM 50005
  6. using namespace std;
  7. struct computer
  8. {
  9. long long x;
  10. long long y;
  11. long long lag = INF;
  12. int p=1;
  13. int id;
  14. bool internet = 0;
  15. };
  16. struct way
  17. {
  18. long long lag;
  19. int num;
  20. };
  21. bool operator < (const way c1, const way c2)
  22. {
  23. return c1.lag > c2.lag;
  24. }
  25. bool cmpx(computer a, computer b)
  26. {
  27. return a.x < b.x;
  28. }
  29. bool cmpy(computer a, computer b)
  30. {
  31. return a.y < b.y;
  32. }
  33. bool cmplag(computer a, computer b)
  34. {
  35. return a.lag < b.lag;
  36. }
  37. bool cmpid(computer a, computer b)
  38. {
  39. return a.id < b.id;
  40. }
  41. way* find(computer a,computer xs[], computer ys[],computer landx[], computer landy[], int n)
  42. {
  43. static way ans[4] = {0};
  44. computer an[5];
  45. //printf("finding\n");
  46. int mid,m=0;
  47. mid = landx[a.id].p;
  48. if (mid != 0)
  49. {
  50. an[m].id = xs[mid - 1].id;
  51. long long d = xs[mid].x -xs[mid - 1].x ;
  52. an[m].lag = a.lag + d;
  53. m++;
  54. }
  55. if (mid != n - 1)
  56. {
  57. an[m].id = xs[mid + 1].id;
  58. long long d = xs[mid + 1].x - xs[mid].x;
  59. an[m].lag = a.lag + d;
  60. m++;
  61. }
  62. mid = landy[a.id].p;
  63. if (mid != 0)
  64. {
  65. an[m].id = ys[mid - 1].id;
  66. long long d = ys[mid].y - ys[mid - 1].y;
  67. an[m].lag = a.lag + d;
  68. m++;
  69. }
  70. if (mid != n - 1)
  71. {
  72. an[m].id = ys[mid + 1].id;
  73. long long d = ys[mid + 1].y - ys[mid].y;
  74. an[m].lag = a.lag + d;
  75. m++;
  76. }
  77. sort(an, an + m,cmplag);
  78. for (int i = 0; i < m; i++)
  79. {
  80. ans[i].lag = an[i].lag;
  81. ans[i].num = an[i].id;
  82. }
  83. for (int i = m; i < 4; i++)
  84. {
  85. ans[i].lag = ans[i].num = 0;
  86. }
  87. return ans;
  88. }
  89. priority_queue<way> map;
  90. int main()
  91. {
  92. int t,i=1 ;
  93. cin >> t;
  94. while (t>=i)
  95. {
  96. int n;
  97. computer my[NUM], xs[NUM], ys[NUM],landx[NUM],landy[NUM];
  98. scanf("%d", &n);
  99. for (int i = 0; i < n; i++)
  100. {
  101. scanf("%Ild %Ild", &my[i].x, &my[i].y);
  102. xs[i].x = ys[i].x = my[i].x;
  103. xs[i].y = ys[i].y = my[i].y;
  104. landy[i].id=landx[i].id=xs[i].id = ys[i].id = my[i].id = i;
  105. }
  106. sort(xs, xs + n, cmpx);
  107. sort(ys, ys + n, cmpy);
  108. for (int i = 0; i < n; i++)
  109. {
  110. landx[i].p = landy[i].p = i;
  111. landx[i].id = xs[i].id;
  112. landy[i].id = ys[i].id;
  113. }
  114. sort(landx, landx + n, cmpid);
  115. sort(landy, landy + n, cmpid);
  116. // give 0 a start push
  117. way ans;
  118. ans.num = 0;
  119. ans.lag = 0;
  120. map.push(ans);
  121. while (!map.empty())
  122. {
  123. way f = map.top();
  124. map.pop();
  125. if (!my[f.num].internet)
  126. {
  127. //printf("give %d a lag of %d\n", f.num, f.lag);
  128. my[f.num].internet = 1;
  129. my[f.num].lag = f.lag;
  130. way* result = find(my[f.num], xs, ys,landx,landy, n);
  131. for (int j = 0; j < 4; j++)
  132. {
  133. map.push(*(result+j));
  134. }
  135. }
  136. }
  137. long long sum = 0;
  138. for (int i = 0; i < n; i++)
  139. {
  140. sum += my[i].lag;
  141. }
  142. printf("Case #%d:\n", i);
  143. i++;
  144. printf("%lld\n", sum);
  145. }
  146. }



点赞 0
举报