url: https://www.luogu.com.cn/problem/P2966

tag:
USACO09DEC,最短路,排序,USACO,2009

思路:
多次询问,点的数据范围小,所以可以用floyd,如果没有点权,那么这道题就是经典的多源汇最短路。为了处理这个点权,我们可以将每一个节点按照点权的大小从小到大排序,然后对于每一个中间节点都是按照从小到大来遍历,这样计算点权的时候,每次中间节点k一定是最大的,所以求点权的最大值时,只要在i,j,k也就是起点终点和用来更新的中间节点之间选择一个较大的即可。

代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. const int N = 300;
  6. int n, m, q;
  7. int ans[N][N], dist[N][N];
  8. struct node {
  9. int val, idx;
  10. } Node[N];
  11. bool cmp (node &a, node &b)
  12. {
  13. return a.val < b.val;
  14. }
  15. int main()
  16. {
  17. cin >> n >> m >> q;
  18. for (int i = 1; i <= n; i ++)
  19. {
  20. cin >> Node[i].val;
  21. Node[i].idx = i;
  22. }
  23. sort(Node + 1, Node + n + 1, cmp);
  24. for (int i = 1; i <= n; i ++)
  25. for (int j = 1; j <= n; j ++)
  26. dist[i][j] = (i == j) ? 0 : 0x3f3f3f3f;
  27. memset(ans, 0x3f, sizeof ans);
  28. for (int i = 1; i <= m; i++)
  29. {
  30. int u, v, w;
  31. cin >> u >> v >> w;
  32. dist[u][v] = dist[v][u] = min(dist[v][u], w);
  33. }
  34. for (int k = 1; k <= n; k ++)
  35. for (int i = 1; i <= n; i ++)
  36. for (int j = 1; j <= n; j ++)
  37. {
  38. dist[Node[i].idx][Node[j].idx] = min(dist[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[k].idx] + dist[Node[k].idx][Node[j].idx]);
  39. ans[Node[i].idx][Node[j].idx] = min(ans[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[j].idx] + max({Node[i].val, Node[j].val, Node[k].val}));
  40. }
  41. while (q --)
  42. {
  43. int a, b;
  44. cin >> a >> b;
  45. cout << ans[a][b] << endl;
  46. }
  47. return 0;
  48. }

url: https://www.luogu.com.cn/problem/P3110

tag:
USACO14DEC,最短路,bfs,USACO,2014

思路:
求三遍最短路,分别是正着求Bessie 和 Elsie 到每个点的最短路,和逆着求终点n到每个点的最短路,然后枚举看从哪个点开始一起走(Bessie 可以背着 Elsie 走)然后到终点的能量最小,更新ans。最后输出ans即可。

代码:

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. typedef pair<int, int> PII;
  7. const int N = 1e5 + 10;
  8. int B, E, P, n, m;
  9. int idx, e[N], ne[N], h[N], w[N];
  10. int distB[N], distE[N], distP[N];
  11. bool st[N];
  12. void add(int a, int b)
  13. {
  14. e[idx] = b;
  15. ne[idx] = h[a];
  16. w[idx] = 1;
  17. h[a] = idx ++;
  18. }
  19. void dijkstra(int s, int dist[])
  20. {
  21. memset(st, 0, sizeof st);
  22. dist[s] = 0;
  23. priority_queue<PII, vector<PII>, greater<PII>> heap;
  24. heap.push({0, s});
  25. while (!heap.empty())
  26. {
  27. auto t = heap.top();
  28. heap.pop();
  29. int ver = t.second;
  30. if (st[ver]) continue;
  31. st[ver] = true;
  32. for (int i = h[ver]; i != -1; i = ne[i])
  33. {
  34. int j = e[i];
  35. if (dist[j] > dist[ver] + w[i])
  36. {
  37. dist[j] = dist[ver] + w[i];
  38. heap.push({dist[j], j});
  39. }
  40. }
  41. }
  42. }
  43. int main()
  44. {
  45. memset(h, -1, sizeof h);
  46. memset(distE, 0x3f, sizeof distE);
  47. memset(distB, 0x3f, sizeof distB);
  48. memset(distP, 0x3f, sizeof distP);
  49. cin >> B >> E >> P >> n >> m;
  50. for (int i = 0; i < m; i ++)
  51. {
  52. int a, b;
  53. cin >> a >> b;
  54. add(a, b), add(b, a);
  55. }
  56. dijkstra(1, distB);
  57. dijkstra(2, distE);
  58. dijkstra(n, distP);
  59. int ans = 0x3f3f3f3f;
  60. for (int i = 1; i <= n; i ++)
  61. {
  62. ans = min(ans, B * distB[i] + E * distE[i] + P * distP[i]);
  63. }
  64. cout << ans;
  65. return 0;
  66. }

url: https://www.luogu.com.cn/problem/P1120

tag:
枚举,搜索,剪枝,dfs

思路:
先从大到小排序,并计算全部木棍长度的和。之后从最长的木棍长开始一直到和的一半枚举,作为原来木棍的长度。然后拿到这个原来的长度之后dfs一下看在有限段的情况下能不能拼凑出全部木棍,可以就输出。最后枚举完全部可能结果后都没答案,就输出长度和作为结果,表示原来只有一根木棍。参考: https://www.luogu.com.cn/article/fxoshw2y

代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int N = 70;
  5. int n, len, m, sum;
  6. int a[N];
  7. int nxt[N];
  8. bool flag = false;
  9. bool st[N];
  10. bool cmp (int &a, int &b)
  11. {
  12. return a > b;
  13. }
  14. void dfs(int k, int last, int rest)
  15. {
  16. int i;
  17. if (!rest) {
  18. if (k == m)
  19. {
  20. flag = true;
  21. return;
  22. }
  23. for (i = 0; i < n; i ++) if (!st[i]) break;
  24. st[i] = true;
  25. dfs(k + 1, i, len - a[i]);
  26. st[i] = false;
  27. if (flag) return;
  28. }
  29. int l = last + 1, r = n - 1;
  30. while (l < r)
  31. {
  32. int mid = (l + r) >> 1;
  33. if (a[mid] <= rest) r = mid;
  34. else l = mid + 1;
  35. }
  36. for (i = l; i < n; i ++)
  37. {
  38. if (!st[i])
  39. {
  40. st[i] = true;
  41. dfs(k, i, rest - a[i]);
  42. st[i] = false;
  43. if (flag) return;
  44. if (rest == a[i] || rest == len) return;
  45. i = nxt[i];
  46. if (i == n - 1) return;
  47. }
  48. }
  49. }
  50. int main()
  51. {
  52. cin >> n;
  53. for (int i = 0; i < n; i ++)
  54. {
  55. cin >> a[i];
  56. sum += a[i];
  57. }
  58. sort(a, a + n, cmp);
  59. nxt[n - 1] = n;
  60. for (int i = n - 2; i >= 0; i --)
  61. {
  62. if (a [i] == a[i + 1]) nxt[i] = nxt[i + 1];
  63. else nxt[i] = i;
  64. }
  65. for (len = a[0]; len <= sum / 2; len ++)
  66. {
  67. if (sum % len != 0) continue;
  68. m = sum / len;
  69. st[0] = true;
  70. dfs(1, 0, len - a[0]);
  71. st[0] = false;
  72. if (flag)
  73. {
  74. cout << len << endl;
  75. return 0;
  76. }
  77. }
  78. cout << sum << endl;
  79. return 0;
  80. }

url: https://www.luogu.com.cn/problem/P4667

tag:
BalticOI 2011,最短路,双端队列,bfs

思路:
用双端队列的bfs,每次走到下一步的时候判断方向是否相同,相同且更新之后路径变小就插到队列前面,不同且更新之后路径变小就插到队列后面。判断是否无解就判断一下终点横纵坐标和是否为奇数,为奇数就无解,因为起点和终点的横纵坐标奇偶性相同(沿对角线走)。
参考: https://www.luogu.com.cn/article/d1fliiql

代码:

  1. #include <iostream>
  2. #include <deque>
  3. #include <cstring>
  4. using namespace std;
  5. const int N = 550;
  6. const int dx[4] = {1, -1, -1, 1};
  7. const int dy[4] = {1, 1, -1, -1};
  8. const char a[5] = "\\/\\/";
  9. const int ix[4] = {0, -1, -1, 0};
  10. const int iy[4] = {0, 0, -1, -1};
  11. deque<int> x;
  12. deque<int> y;
  13. int n, m;
  14. char d[N][N];
  15. int vis[N][N];
  16. void bfs()
  17. {
  18. memset(vis, 0x3f, sizeof vis);
  19. x.push_back(0);
  20. y.push_back(0);
  21. vis[0][0] = 0;
  22. while (!x.empty()) {
  23. int xx = x.front();
  24. int yy = y.front();
  25. x.pop_front();
  26. y.pop_front();
  27. for (int i = 0; i < 4; i++) {
  28. int dnx = xx + dx[i];
  29. int dny = yy + dy[i];
  30. int inx = xx + ix[i];
  31. int iny = yy + iy[i];
  32. if (dnx >= 0 && dnx <= n && dny >= 0 && dny <= m) {
  33. if (a[i] != d[inx][iny]) {
  34. int t = vis[xx][yy] + 1;
  35. if (t < vis[dnx][dny]) {
  36. x.push_back(dnx);
  37. y.push_back(dny);
  38. vis[dnx][dny] = t;
  39. }
  40. } else {
  41. int t = vis[xx][yy];
  42. if (t < vis[dnx][dny]) {
  43. x.push_front(dnx);
  44. y.push_front(dny);
  45. vis[dnx][dny] = t;
  46. }
  47. }
  48. }
  49. }
  50. }
  51. cout << vis[n][m] << endl;
  52. }
  53. int main()
  54. {
  55. cin >> n >> m;
  56. for (int i = 0; i < n; i ++) cin >> d[i];
  57. if ((n + m) % 2) cout << "NO SOLUTION" << endl;
  58. else bfs();
  59. return 0;
  60. }

url: https://www.luogu.com.cn/problem/P1119

tag:
图论,枚举,最短路

思路:
这道题可以用floyd算法来做,每次询问,都将当前这个时间可以重建完的村庄用floyd算法更新一下所有点的最短路。最后判断一下这个询问的两个村庄是否重建完以及是否可以联通,如果重建完并且联通就输出最短路,否则输出-1

代码:

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int N = 220;
  5. int n, m, q;
  6. int f[N][N];
  7. int a[N];
  8. inline void update(int k)
  9. {
  10. for (int i = 0; i < n; i ++)
  11. for (int j = 0; j< n; j ++)
  12. f[i][j] = f[j][i] = min(f[i][j], f[i][k] + f[k][j]);
  13. }
  14. int main()
  15. {
  16. cin >> n >> m;
  17. for (int i = 0; i < n; i ++) cin >> a[i];
  18. for (int i = 0; i < n; i ++)
  19. {
  20. for (int j = 0; j < n; j ++) f[i][j] = 0x3f3f3f3f;
  21. f[i][i] = 0;
  22. }
  23. for (int i = 0; i < m; i ++)
  24. {
  25. int x, b, w;
  26. cin >> x >> b >> w;
  27. f[x][b] = f[b][x] = w;
  28. }
  29. cin >> q;
  30. int idx = 0;
  31. for (int i = 0; i < q; i ++)
  32. {
  33. int x, y, z;
  34. cin >> x >> y >> z;
  35. while (a[idx] <= z && idx < n)
  36. {
  37. update(idx);
  38. idx ++;
  39. }
  40. if (a[x] > z || a[y] > z) cout << -1 << endl;
  41. else if (f[x][y] == 0x3f3f3f3f) cout << -1 << endl;
  42. else cout << f[x][y] << endl;
  43. }
  44. return 0;
  45. }