[关闭]
@Dmaxiya 2020-08-25T00:40:29.000000Z 字数 17011 阅读 1083

图论练习题解

Hello_World

2月19日 树/图上 bfs/dfs 练习题解

A. Coloring a Tree

题意

给一棵 个节点的无色的树上色，对于每一次上色，选择一个点后，可以将这个点所对应的子树都图上同一种颜色，现在给定树的结构，问最少需要上几次颜色，能够使得每个节点的颜色和题目表示的颜色相同。

数据范围

题解

从根节点（下标为 的节点）开始往下 ，只要父节点和子节点的颜色不同，就将答案加一，最后输出答案。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 10000 + 100;
  22. int n, tmp;
  23. int color[maxn];
  24. vector<int> G[maxn];
  26. int dfs(int x) {
  27.     int ret = 0;
  28.     int len = G[x].size();
  29.     for(int i = 0; i < len; ++i) {
  30.         int pos = G[x][i];
  31.         ret += dfs(pos);
  32.         ret += (color[pos] != color[x]);
  33.     }
  34.     return ret;
  35. }
  37. int main() {
  38.     #ifdef LOCAL
  39.     freopen("test.txt", "r", stdin);
  40. //    freopen("out.txt", "w", stdout);
  41.     #endif // LOCAL
  42.     ios::sync_with_stdio(false);
  44.     while(scanf("%d", &n) != EOF) {
  45.         for(int i = 1; i <= n; ++i) {
  46.             G[i].clear();
  47.         }
  48.         for(int i = 2; i <= n; ++i) {
  49.             scanf("%d", &tmp);
  50.             G[tmp].push_back(i);
  51.         }
  52.         for(int i = 1; i <= n; ++i) {
  53.             scanf("%d", &color[i]);
  54.         }
  55.         printf("%d\n", dfs(1) + 1);
  56.     }
  58.     return 0;
  59. }

B. 确定比赛名次

题解

从所有的胜利者向失败者连一条有向边，然后进行拓扑排序（最开始将所有入度为零的点加入队列，再进行宽搜，对于每个弹出队列的点，将它的后继节点的入度减一，如果某个后继节点的入度为零，则进入队列），由于题目要求输出字典序最小的，所以将队列改成优先队列即可。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 600;
  22. int n, m, u, v;
  23. int cnt, ans[maxn];
  24. vector<int> G[maxn];
  25. int deg[maxn];
  26. priority_queue<int, vector<int>, greater<int> > que;
  28. void topsort() {
  29.     cnt = 0;
  30.     for(int i = 1; i <= n; ++i) {
  31.         if(deg[i] == 0) {
  32.             que.push(i);
  33.         }
  34.     }
  35.     while(!que.empty()) {
  36.         int tmp = que.top();
  37.         que.pop();
  38.         ans[cnt++] = tmp;
  39.         int len = G[tmp].size();
  40.         for(int i = 0; i < len; ++i) {
  41.             int pos = G[tmp][i];
  42.             --deg[pos];
  43.             if(deg[pos] == 0) {
  44.                 que.push(pos);
  45.             }
  46.         }
  47.     }
  48. }
  50. int main() {
  51.     #ifdef LOCAL
  52.     freopen("test.txt", "r", stdin);
  53. //    freopen("out.txt", "w", stdout);
  54.     #endif // LOCAL
  55.     ios::sync_with_stdio(false);
  57.     while(scanf("%d%d", &n, &m) != EOF) {
  58.         for(int i = 1; i <= n; ++i) {
  59.             G[i].clear();
  60.         }
  61.         for(int i = 0; i < m; ++i) {
  62.             scanf("%d%d", &u, &v);
  63.             G[u].push_back(v);
  64.             ++deg[v];
  65.         }
  66.         topsort();
  67.         for(int i = 0; i < cnt; ++i) {
  68.             if(i != 0) {
  69.                 printf(" ");
  70.             }
  71.             printf("%d", ans[i]);
  72.         }
  73.         printf("\n");
  74.     }
  76.     return 0;
  77. }

C. Labyrinth

题意

故事太长略去，就是在一个 的迷宫内找到任意两点最短距离的最大值。

数据范围

题解

这题是裸的求树的直径（从任意一点开始，找到离这个点最远的点 ，再从 点找到另一个离 点最远的点 ， 和 之间的距离就是树的直径）的题目，但是树上是没有环的，所以求路径长度就是最短路径，这题相当于是有环的图，所以就按照题目要求求出任意两点最短路径，作为“树”上距离，然后求直径就行了。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 1000 + 100;
  22. struct Node {
  23.     int x, y;
  24.     Node() {}
  25.     Node(int xx, int yy) {
  26.         x = xx;
  27.         y = yy;
  28.     }
  29. };
  30. int T, n, m, x, y;
  31. char str[maxn][maxn];
  32. queue<Node> que;
  33. int step[maxn][maxn];
  34. const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
  36. bool in(int x, int y) {
  37.     return x >= 0 && x < n && y >= 0 && y < m;
  38. }
  40. void bfs() {
  41.     memset(step, -1, sizeof(step));
  42.     step[x][y] = 0;
  43.     que.push(Node(x, y));
  44.     while(!que.empty()) {
  45.         Node tmp = que.front();
  46.         que.pop();
  47.         for(int i = 0; i < 4; ++i) {
  48.             int xx = tmp.x + dir[i][0];
  49.             int yy = tmp.y + dir[i][1];
  50.             if(in(xx, yy) && step[xx][yy] == -1 && str[xx][yy] == '.') {
  51.                 step[xx][yy] = step[tmp.x][tmp.y] + 1;
  52.                 que.push(Node(xx, yy));
  53.                 if(step[xx][yy] > step[x][y]) {
  54.                     x = xx;
  55.                     y = yy;
  56.                 }
  57.             }
  58.         }
  59.     }
  60. }
  62. int main() {
  63.     #ifdef LOCAL
  64.     freopen("test.txt", "r", stdin);
  65. //    freopen("out.txt", "w", stdout);
  66.     #endif // LOCAL
  67.     ios::sync_with_stdio(false);
  69.     scanf("%d", &T);
  70.     while(T--) {
  71.         scanf("%d%d", &m, &n);
  72.         for(int i = 0; i < n; ++i) {
  73.             scanf("%s", str[i]);
  74.             for(int j = 0; j < m; ++j) {
  75.                 if(str[i][j] == '.') {
  76.                     x = i;
  77.                     y = j;
  78.                 }
  79.             }
  80.         }
  81.         bfs();
  82.         bfs();
  83.         printf("Maximum rope length is %d.\n", step[x][y]);
  84.     }
  86.     return 0;
  87. }

2月20日 欧拉路练习

A. 欧拉路·一

题解

题解题目已经给出。
这题数据出水了，没有用并查集判连通块也被你们过了，但是后面如果碰到判断欧拉路的问题，一定要记得先判连通块。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 10000 + 100;
  22. int n, m, u, v;
  23. bool flag;
  24. int fa[maxn], deg[maxn];
  26. void Init() {
  27.     flag = true;
  28.     memset(deg, 0, sizeof(deg));
  29.     for(int i = 1; i <= n; ++i) {
  30.         fa[i] = i;
  31.     }
  32. }
  34. int Find(int x) {
  35.     return (x == fa[x]? x: fa[x] = Find(fa[x]));
  36. }
  38. void unit(int x, int y) {
  39.     int xx = Find(x);
  40.     int yy = Find(y);
  41.     fa[xx] = yy;
  42. }
  44. int main() {
  45.     #ifdef LOCAL
  46.     freopen("test.txt", "r", stdin);
  47. //    freopen("out.txt", "w", stdout);
  48.     #endif // LOCAL
  49.     ios::sync_with_stdio(false);
  51.     while(scanf("%d%d", &n, &m) != EOF) {
  52.         Init();
  53.         for(int i = 0; i < m; ++i) {
  54.             scanf("%d%d", &u, &v);
  55.             unit(u, v);
  56.             ++deg[u];
  57.             ++deg[v];
  58.         }
  59.         for(int i = 2; i <= n; ++i) {
  60.             if(Find(i) != Find(1)) {
  61.                 flag = false;
  62.                 break;
  63.             }
  64.         }
  65.         if(!flag) {
  66.             printf("Part\n");
  67.             continue;
  68.         }
  69.         int cnt = 0;
  70.         for(int i = 1; i <= n; ++i) {
  71.             cnt += (deg[i] % 2);
  72.         }
  73.         if(cnt == 0 || cnt == 2) {
  74.             printf("Full\n");
  75.         } else {
  76.             printf("Part\n");
  77.         }
  78.     }
  80.     return 0;
  81. }

B. 欧拉路·二

题解

题解题目已经给出，主要代码也在第一页给出。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 5000 + 100;
  22. struct Node {
  23.     int pos;
  24.     int Index;
  25.     Node() {}
  26.     Node(int p, int I) {
  27.         pos = p;
  28.         Index = I;
  29.     }
  30. };
  31. struct Edge {
  32.     int u, v;
  33. };
  34. int n, m, cnt, u, v;
  35. int deg[maxn];
  36. bool vis[maxn];
  37. Edge ans[maxn];
  38. vector<Node> G[maxn];
  40. void dfs(int x) {
  41.     int len = G[x].size();
  42.     for(int i = 0; i < len; ++i) {
  43.         int pos = G[x][i].pos;
  44.         int Index = G[x][i].Index;
  45.         if(!vis[Index]) {
  46.             vis[Index] = true;
  47.             dfs(pos);
  48.             ans[cnt].u = x;
  49.             ans[cnt++].v = pos;
  50.         }
  51.     }
  52. }
  54. int main() {
  55.     #ifdef LOCAL
  56.     freopen("test.txt", "r", stdin);
  57. //    freopen("out.txt", "w", stdout);
  58.     #endif // LOCAL
  59.     ios::sync_with_stdio(false);
  61.     while(scanf("%d%d", &n, &m) != EOF) {
  62.         cnt = 0;
  63.         memset(vis, 0, sizeof(vis));
  64.         for(int i = 1; i <= n; ++i) {
  65.             G[i].clear();
  66.             deg[i] = 0;
  67.         }
  68.         for(int i = 0; i < m; ++i) {
  69.             scanf("%d%d", &u, &v);
  70.             G[u].push_back(Node(v, i));
  71.             G[v].push_back(Node(u, i));
  72.             ++deg[u];
  73.             ++deg[v];
  74.         }
  75.         for(int i = 1; i <= n; ++i) {
  76.             if(deg[i] % 2 == 1) {
  77.                 u = i;
  78.                 break;
  79.             }
  80.         }
  81.         dfs(u);
  82.         for(int i = cnt - 1; i >= 0; --i) {
  83.             printf("%d ", ans[i].u);
  84.         }
  85.         printf("%d\n", ans[0].v);
  86.     }
  88.     return 0;
  89. }

C. 欧拉路·三

题解

题解题目已经给出。这题涉及到位运算可能不太熟悉，其实位运算的 ~ 和逻辑运算符的 非常类似，只是将数字转化为二进制数后进行按位“与或非”，这里以 和 为例：


还有两个是左移和右移运算符，对于正数，左移运算符将 的所有二进制位向高位移动，溢出部分直接舍去，低位补 ，右移运算符将 的所有二进制位向低位移动，溢出部分直接社区，高位补 ，负数只是将补 改为补 ，这里以 为例：

还有一个不太好理解的可能就是为什么题目用那样的构图方法，我看起来感觉题目已经说得很清楚了，如果有什么问题的话可以私戳我，说明具体是哪个地方没看懂。
这题的过题代码就加一些注释吧。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = (1 << 15); // 实际上只需要 1 << 14，可以想一想为什么
  22. struct Node {
  23.     int pos;    // 表示节点所代表的数字，就是图示中的两位二进制数，范围：[0，(1<<14)-1]
  24.     int weight; // 表示边权，就是图示中的三位二进制数，范围：[0,(1<<15)-1]
  25.     Node() {}
  26.     Node(int p, int w) {
  27.         pos = p;
  28.         weight = w;
  29.     }
  30. };
  31. int n, cnt;
  32. int ans[maxn];
  33. vector<Node> G[maxn];
  34. bool vis[maxn];
  36. // 寻找欧拉路经
  37. void dfs(int x) {
  38.     int len = G[x].size();
  39.     for(int i = 0; i < len; ++i) {
  40.         int pos = G[x][i].pos;
  41.         int weight = G[x][i].weight;
  42.         if(!vis[weight]) {
  43.             vis[weight] = true;
  44.             dfs(pos);
  45.             ans[cnt++] = weight;
  46.         }
  47.     }
  48. }
  50. int main() {
  51.     #ifdef LOCAL
  52.     freopen("test.txt", "r", stdin);
  53. //    freopen("out.txt", "w", stdout);
  54.     #endif // LOCAL
  55.     ios::sync_with_stdio(false);
  57.     while(scanf("%d", &n) != EOF) {
  58.         cnt = 0;
  59.         memset(vis, 0, sizeof(vis));
  60.         int up = (1 << (n - 1));    // 节点范围为 [0,(1<<(n-1))-1]
  61.         for(int i = 0; i < up; ++i) {
  62.             G[i].clear();
  63.         }
  64.         for(int i = 0; i < up; ++i) {
  65.             G[i].push_back(Node(((i << 1) & (~up)), (i << 1)));
  66.             G[i].push_back(Node((((i << 1) & (~up)) | 1), (i << 1 | 1)));
  67.             // 这里取 ~up 只是一巧合，实际上应该是 ~(1<<(n-1))（恰好等于 up），与上这个值的作用是去掉 i<<1 的最高位
  68.         }
  69.         dfs(0);
  70.         for(int i = cnt - 1; i >= 0; --i) {
  71.             printf("%d", (ans[i] & 1));
  72.             // 输出欧拉路径，其实这里于上的值可以为 [1,1<<1,1<<2,...,1<<(n-1)]，因为是环上的 01 是循环的，所以取边权的任意位都是对的
  73.         }
  74.         printf("\n");
  75.     }
  77.     return 0;
  78. }

2月21日 dij & floyd 练习

A. 畅通工程续

题解

单源最短路裸题。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 300;
  22. struct Node {
  23.     int pos;
  24.     int dis;
  25.     Node() {}
  26.     Node(int p, int d) {
  27.         pos = p;
  28.         dis = d;
  29.     }
  30. };
  31. bool operator<(const Node &a, const Node &b) {
  32.     return a.dis > b.dis;
  33. }
  34. int INF;
  35. int n, m, u, v, d, s, t;
  36. int dis[maxn];
  37. vector<Node> G[maxn];
  38. priority_queue<Node> que;
  40. void dij(int s) {
  41.     memset(dis, 0x3f, sizeof(dis));
  42.     dis[s] = 0;
  43.     que.push(Node(s, 0));
  44.     while(!que.empty()) {
  45.         Node tmp = que.top();
  46.         que.pop();
  47.         int len = G[tmp.pos].size();
  48.         for(int i = 0; i < len; ++i) {
  49.             int pos = G[tmp.pos][i].pos;
  50.             d = G[tmp.pos][i].dis;
  51.             if(dis[pos] > dis[tmp.pos] + d) {
  52.                 dis[pos] = dis[tmp.pos] + d;
  53.                 que.push(Node(pos, dis[pos]));
  54.             }
  55.         }
  56.     }
  57. }
  59. int main() {
  60.     #ifdef LOCAL
  61.     freopen("test.txt", "r", stdin);
  62. //    freopen("out.txt", "w", stdout);
  63.     #endif // LOCAL
  64.     ios::sync_with_stdio(false);
  66.     memset(&INF, 0x3f, sizeof(int));
  67.     while(scanf("%d%d", &n, &m) != EOF) {
  68.         for(int i = 0; i < n; ++i) {
  69.             G[i].clear();
  70.         }
  71.         for(int i = 0; i < m; ++i) {
  72.             scanf("%d%d%d", &u, &v, &d);
  73.             G[u].push_back(Node(v, d));
  74.             G[v].push_back(Node(u, d));
  75.         }
  76.         scanf("%d%d", &s, &t);
  77.         dij(s);
  78.         if(dis[t] == INF) {
  79.             printf("-1\n");
  80.         } else {
  81.             printf("%d\n", dis[t]);
  82.         }
  83.     }
  85.     return 0;
  86. }

B. Invitation Cards

题意

故事太长。问题就是在一个 个节点， 条边的有向图上，求从起点到所有车站的花费 ，以及从所有车站回到起点的花费总和。

数据范围

题解

找起点到其他所有点的最短路，就直接从起点开始跑一遍最短路，找所有其他点到起点的花费总和，可以将所有边反向，然后从起点开始跑一遍最短路。注意虽然每一条最短路最大值为 ，但是所有最短路的总和就要爆 了，所以计算最短路的过程中可以用 ，而求和的时候必须用 储存。
一不小心找了一道卡常题，失误失误，不过看你们被 的地方好像不是很难处理，虽然数据量比较大，但是不卡 ，用 又不取消同步被卡，就是自己的问题了。这题我被卡的地方是开了两个邻接链表数组，只开一个的话就能过，比较玄学就是了。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 1000000 + 100;
  22. struct Node {
  23.     int pos;
  24.     int dis;
  25.     Node() {}
  26.     Node(int p, int d) {
  27.         pos = p;
  28.         dis = d;
  29.     }
  30. };
  31. bool operator<(const Node &a, const Node &b) {
  32.     return a.dis > b.dis;
  33. }
  34. int T, n, m;
  35. int u[maxn], v[maxn], d[maxn];
  36. LL ans;
  37. int dis[maxn];
  38. vector<Node> G[maxn];
  39. priority_queue<Node> que;
  41. void Clear() {
  42.     for(int i = 1; i <= n; ++i) {
  43.         G[i].clear();
  44.     }
  45. }
  47. void dij(int s) {
  48.     memset(dis, 0x3f, sizeof(int) * (n + 1));
  49.     dis[s] = 0;
  50.     que.push(Node(s, 0));
  51.     while(!que.empty()) {
  52.         Node tmp = que.top();
  53.         que.pop();
  54.         int len = G[tmp.pos].size();
  55.         for(int i = 0; i < len; ++i) {
  56.             int pos = G[tmp.pos][i].pos;
  57.             int d = G[tmp.pos][i].dis;
  58.             if(dis[pos] > tmp.dis + d) {
  59.                 dis[pos] = tmp.dis + d;
  60.                 que.push(Node(pos, dis[pos]));
  61.             }
  62.         }
  63.     }
  64.     for(int i = 1; i <= n; ++i) {
  65.         ans += dis[i];
  66.     }
  67. }
  69. int main() {
  70.     #ifdef LOCAL
  71.     freopen("test.txt", "r", stdin);
  72. //    freopen("out.txt", "w", stdout);
  73.     #endif // LOCAL
  74.     ios::sync_with_stdio(false);
  76.     scanf("%d", &T);
  77.     while(T--) {
  78.         ans = 0;
  79.         scanf("%d%d", &n, &m);
  80.         Clear();
  81.         for(int i = 0; i < m; ++i) {
  82.             scanf("%d%d%d", &u[i], &v[i], &d[i]);
  83.             G[u[i]].push_back(Node(v[i], d[i]));
  84.         }
  85.         dij(1);
  86.         Clear();
  87.         for(int i = 0; i < m; ++i) {
  88.             G[v[i]].push_back(Node(u[i], d[i]));
  89.         }
  90.         dij(1);
  91.         printf("%lld\n", ans);
  92.     }
  94.     return 0;
  95. }

C. Choose the best route

题意

在一个 个节点， 条边的有向图中，从给定的 个点中，找到这些点到终点 最短路径的最小值。

数据范围

题解

同样地，每条边都反向构图，然后从 点开始跑一遍最短路。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 1000 + 100;
  22. struct Node {
  23.     int pos;
  24.     int dis;
  25.     Node() {}
  26.     Node(int p, int d) {
  27.         pos = p;
  28.         dis = d;
  29.     }
  30. };
  31. bool operator<(const Node &a, const Node &b) {
  32.     return a.dis > b.dis;
  33. }
  34. int INF;
  35. int n, m, s, u, v, d, w, ans;
  36. int dis[maxn];
  37. vector<Node> G[maxn];
  38. priority_queue<Node> que;
  40. void dij() {
  41.     dis[s] = 0;
  42.     que.push(Node(s, 0));
  43.     while(!que.empty()) {
  44.         Node tmp = que.top();
  45.         que.pop();
  46.         int len = G[tmp.pos].size();
  47.         for(int i = 0; i < len; ++i) {
  48.             int pos = G[tmp.pos][i].pos;
  49.             d = G[tmp.pos][i].dis;
  50.             if(dis[pos] > tmp.dis + d) {
  51.                 dis[pos] = tmp.dis + d;
  52.                 que.push(Node(pos, dis[pos]));
  53.             }
  54.         }
  55.     }
  56. }
  58. int main() {
  59.     #ifdef LOCAL
  60.     freopen("test.txt", "r", stdin);
  61. //    freopen("out.txt", "w", stdout);
  62.     #endif // LOCAL
  63.     ios::sync_with_stdio(false);
  65.     memset(&INF, 0x3f, sizeof(int));
  66.     while(scanf("%d%d%d", &n, &m, &s) != EOF) {
  67.         for(int i = 1; i <= n; ++i) {
  68.             G[i].clear();
  69.             dis[i] = INF;
  70.         }
  71.         for(int i = 0; i < m; ++i) {
  72.             scanf("%d%d%d", &u, &v, &d);
  73.             G[v].push_back(Node(u, d));
  74.         }
  75.         dij();
  76.         ans = INF;
  77.         scanf("%d", &w);
  78.         for(int i = 0; i < w; ++i) {
  79.             scanf("%d", &u);
  80.             ans = min(ans, dis[u]);
  81.         }
  82.         if(ans == INF) {
  83.             printf("-1\n");
  84.         } else {
  85.             printf("%d\n", ans);
  86.         }
  87.     }
  89.     return 0;
  90. }

D. find the safest road

题解

裸题，但是不是多源最短路，而是最长路，安全系数的计算方式为乘法。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const double eps = 1e-6;
  22. const int maxn = 1000 + 100;
  23. int n, q, u, v;
  24. double G[maxn][maxn];
  26. bool zero(const double &x) {
  27.     return fabs(x) < eps;
  28. }
  30. int main() {
  31.     #ifdef LOCAL
  32.     freopen("test.txt", "r", stdin);
  33. //    freopen("out.txt", "w", stdout);
  34.     #endif // LOCAL
  35.     ios::sync_with_stdio(false);
  37.     while(scanf("%d", &n) != EOF) {
  38.         for(int i = 1; i <= n; ++i) {
  39.             for(int j = 1; j <= n; ++j) {
  40.                 scanf("%lf", &G[i][j]);
  41.             }
  42.         }
  43.         for(int k = 1; k <= n; ++k) {
  44.             for(int i = 1; i <= n; ++i) {
  45.                 for(int j = 1; j <= n; ++j) {
  46.                     G[i][j] = max(G[i][j], G[i][k] * G[k][j]);
  47.                 }
  48.             }
  49.         }
  50.         scanf("%d", &q);
  51.         for(int i = 0; i < q; ++i) {
  52.             scanf("%d%d", &u, &v);
  53.             if(zero(G[u][v])) {
  54.                 printf("What a pity!\n");
  55.             } else {
  56.                 printf("%.3f\n", G[u][v]);
  57.             }
  58.         }
  59.     }
  61.     return 0;
  62. }

2月22日 并查集&最小生成树练习

A. D-City

题意

在一个 个节点的图上， 将按顺序破坏图上所有的 条边，问每破坏一条边，剩余的连通块有多少个。

数据范围

题解

将破坏的顺序反过来，变成加边的顺序，就可以用并查集统计连通块的个数了。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 10000 + 100;
  22. const int maxm = 100000 + 100;
  23. struct Node {
  24.     int u, v;
  25. };
  26. int n, m;
  27. Node node[maxm];
  28. int fa[maxn], ans[maxm];
  30. void Init() {
  31.     for(int i = 0; i < n; ++i) {
  32.         fa[i] = i;
  33.     }
  34. }
  36. int Find(int x) {
  37.     return (x == fa[x]? x: fa[x] = Find(fa[x]));
  38. }
  40. void unit(int x, int y) {
  41.     int xx = Find(x);
  42.     int yy = Find(y);
  43.     fa[xx] = yy;
  44. }
  46. int main() {
  47.     #ifdef LOCAL
  48.     freopen("test.txt", "r", stdin);
  49. //    freopen("out.txt", "w", stdout);
  50.     #endif // LOCAL
  51.     ios::sync_with_stdio(false);
  53.     while(scanf("%d%d", &n, &m) != EOF) {
  54.         Init();
  55.         for(int i = 1; i <= m; ++i) {
  56.             scanf("%d%d", &node[i].u, &node[i].v);
  57.         }
  58.         int cnt = n;
  59.         ans[m] = cnt;
  60.         for(int i = m; i >= 1; --i) {
  61.             int u = node[i].u;
  62.             int v = node[i].v;
  63.             if(Find(u) != Find(v)) {
  64.                 --cnt;
  65.                 unit(u, v);
  66.             }
  67.             ans[i - 1] = cnt;
  68.         }
  69.         for(int i = 1; i <= m; ++i) {
  70.             printf("%d\n", ans[i]);
  71.         }
  72.     }
  74.     return 0;
  75. }

B. 畅通工程

题解

裸的最小生成树问题，用克鲁斯卡尔就可以解决。最后注意要先判是否能够全连通。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 200;
  22. struct Node {
  23.     int u, v;
  24.     int dis;
  25. };
  26. bool operator<(const Node &a, const Node &b) {
  27.     return a.dis < b.dis;
  28. }
  29. int n, m, ans;
  30. int fa[maxn];
  31. Node node[maxn];
  33. void Init() {
  34.     ans = 0;
  35.     for(int i = 1; i <= n; ++i) {
  36.         fa[i] = i;
  37.     }
  38. }
  40. int Find(int x) {
  41.     return (x == fa[x]? x: fa[x] = Find(fa[x]));
  42. }
  44. void unit(int x, int y) {
  45.     int xx = Find(x);
  46.     int yy = Find(y);
  47.     fa[xx] = yy;
  48. }
  50. int main() {
  51.     #ifdef LOCAL
  52.     freopen("test.txt", "r", stdin);
  53. //    freopen("out.txt", "w", stdout);
  54.     #endif // LOCAL
  55.     ios::sync_with_stdio(false);
  57.     while(scanf("%d%d", &m, &n), m != 0) {
  58.         Init();
  59.         for(int i = 0; i < m; ++i) {
  60.             scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].dis);
  61.         }
  62.         sort(node, node + m);
  63.         for(int i = 0; i < m; ++i) {
  64.             int u = node[i].u;
  65.             int v = node[i].v;
  66.             if(Find(u) != Find(v)) {
  67.                 unit(u, v);
  68.                 ans += node[i].dis;
  69.             }
  70.         }
  71.         int f = Find(1);
  72.         bool flag = true;
  73.         for(int i = 1; i <= n; ++i) {
  74.             if(Find(i) != f) {
  75.                 flag = false;
  76.                 break;
  77.             }
  78.         }
  79.         if(flag) {
  80.             printf("%d\n", ans);
  81.         } else {
  82.             printf("?\n");
  83.         }
  84.     }
  86.     return 0;
  87. }

C. Arctic Network

题意

有 个卫星和 个哨站，如果某一个位于点 的哨站上有卫星，就可以与其他任何一个有卫星的哨站相互通信，如果没有，就只能和距离自己不超过 的其他哨站通信，问要使得所有哨站之间相互通信，这个 的最小值是多少。

数据范围

题解

要求最短的 ，就是在完全图上求最小生成树上距离最大的边，但是由于有卫星的哨站可以与任何其他有卫星的哨站联系，而不受距离限制，所以如果把每个有卫星的哨站分到不同的连通块里，也能使所有哨站相互通信。为使 最小，可以将生成树中最长的几条边去掉，去完边后，在不同的连通块内的任意一点放卫星。由于树上删边，删一条边多一个连通块，所以最多可以删 条边。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 600;
  22. struct Node {
  23.     int u, v;
  24.     int dis;
  25. };
  26. bool operator<(const Node &a, const Node &b) {
  27.     return a.dis < b.dis;
  28. }
  29. struct Point {
  30.     int x, y;
  31. };
  32. double ans;
  33. int T, s, p, cnt;
  34. Node node[maxn * maxn];
  35. Point point[maxn];
  36. int fa[maxn];
  38. int get_dis(int i, int j) {
  39.     int dx = point[i].x - point[j].x;
  40.     int dy = point[i].y - point[j].y;
  41.     return dx * dx + dy * dy;
  42. }
  44. void Init() {
  45.     for(int i = 0; i < p; ++i) {
  46.         fa[i] = i;
  47.     }
  48. }
  50. int Find(int x) {
  51.     return (x == fa[x]? x: fa[x] = Find(fa[x]));
  52. }
  54. void unit(int x, int y) {
  55.     int xx = Find(x);
  56.     int yy = Find(y);
  57.     fa[xx] = yy;
  58. }
  60. int main() {
  61.     #ifdef LOCAL
  62.     freopen("test.txt", "r", stdin);
  63. //    freopen("out.txt", "w", stdout);
  64.     #endif // LOCAL
  65.     ios::sync_with_stdio(false);
  67.     scanf("%d", &T);
  68.     while(T--) {
  69.         cnt = 0;
  70.         scanf("%d%d", &s, &p);
  71.         Init();
  72.         for(int i = 0; i < p; ++i) {
  73.             scanf("%d%d", &point[i].x, &point[i].y);
  74.             for(int j = 0; j < i; ++j) {
  75.                 node[cnt].u = i;
  76.                 node[cnt].v = j;
  77.                 node[cnt].dis = get_dis(i, j);
  78.                 ++cnt;
  79.             }
  80.         }
  81.         sort(node, node + cnt);
  82.         int cnt_ans = 0;
  83.         for(int i = 0; i < cnt; ++i) {
  84.             int u = node[i].u;
  85.             int v = node[i].v;
  86.             if(Find(u) != Find(v)) {
  87.                 ++cnt_ans;
  88.                 unit(u, v);
  89.                 if(cnt_ans == p - s) {
  90.                     ans = sqrt((double)node[i].dis);
  91.                     break;
  92.                 }
  93.             }
  94.         }
  95.         printf("%.2f\n", ans);
  96.     }
  98.     return 0;
  99. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注