devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图论（蓝桥杯 C++ 题目 代码 注解）

作者：很楠不爱3 | 2024-04-01 11:09:12

赞

踩

图论（蓝桥杯 C++ 题目 代码 注解）

目录

迪杰斯特拉模板（用来求一个点出发到其它点的最短距离）：

克鲁斯卡尔模板（用来求最小生成树）：

题目一（蓝桥王国）：

题目二（随机数据下的最短路径）： 

题目三（出差）：

题目四（聪明的猴子）：

 题目六（机房）：

迪杰斯特拉模板（用来求一个点出发到其它点的最短距离）：

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
  8. struct  node
  9. {
  10.     ll v, w;
  11.     bool operator <(const node& y) const//重载一个<,用于优先队列排序
  12.     {
  13.         return w > y.w;//小到大
  14.     }
  15. };
  16. int n, m;
  17. priority_queue<node>q;
  18. vector<node> e[N];
  19. ll dis[N], vis[N];
  20. void Dij()
  21. {
  22.     dis[1] = 0;//从1号点出发，表示从1到1距离为0
  23.     q.push({ 1,dis[1] });//1号点以及到1的距离入队
  24.     while (q.size())
  25.     {
  26.         int u = q.top().v;//取最小边相连的点出队
  27.         q.pop();
  28.         if (vis[u])//访问过则跳过
  29.             continue;
  30.         vis[u] = 1;//没访问赋为访问
  31.         for (auto i : e[u])//遍历以u为出发点的边
  32.         {
  33.             int v = i.v, w = i.w;//取其相连的点及权值
  34.             if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
  35.             {
  36.                 dis[v] = dis[u] + w;
  37.                 q.push({ v,dis[v] });//v点以及到v的距离
  38.             }
  39.         }
  40.     }
  41.  
  42. }
  43. int main()
  44. {
  45.     cin >> n >> m;
  46.     fill(dis+1, dis+1+n, inf);//赋值一个无穷大，表示没有连接
  47.     for (int i = 1; i <= m; i++)
  48.     {
  49.         int x, y, w;
  50.         cin >> x >> y >> w;
  51.         e[x].push_back({ y,w });//存入以x出发到y，权值为w
  52.     }
  53.     Dij();
  54. }

克鲁斯卡尔模板（用来求最小生成树）：

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6. const int N = 1e3+20;
  7. int m, n;
  8. int f[N];
  9. struct edge
  10. {
  11.     int v1, v2;
  12.     double w;
  13. };
  14. vector<edge> e;
  15. int find(int k)//查找
  16. {
  17.     if (f[k] == k)
  18.         return k;
  19.     return f[k] = find(f[k]);
  20. }
  21. void  merge(int x, int y)//合并
  22. {
  23.   x=find(x),y=find(y);
  24.     if (x!= y)
  25.         f[x] = f[y];
  26. }
  27. bool cmp(edge a, edge b)
  28. {
  29.     return a.w < b.w;
  30. }
  31. int main()
  32. {
  33.     cin >> n;
  34.     for (int j = 1; j <= n; j++)
  35.     {
  36.         f[j] = j;//初始化并查集根
  37.     }
  38.     cin>>m;
  39.         for (int j = 1; j <= m; j++)//添加边
  40.         {
  41.             int v1,v2,w;
  42.             cin>>v1>>v2>>w;
  43.             e.push_back({ v1, v2, w });
  44.         }
  45.     sort(e.begin(), e.end(), cmp);//边从小到大排序
  46.     int cnt=0;
  47.     for (int i = 0; i < e.size(); i++)
  48.     {
  49.         if (find(e[i].v1) != find(e[i].v2))//不属于一个集合
  50.         {
  51.             merge(e[i].v1, e[i].v2);//合并
  52.             cnt++;
  53.         }
  54.         if (cnt == n-1)//n个点只需要n-1条边，选取n-1条边后，跳出循环
  55.             break;
  56.     }
  57. }

题目一（蓝桥王国）：

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
  8. struct  node
  9. {
  10.     ll v, w;
  11.     bool operator <(const node& y) const//重载一个<,用于优先队列排序
  12.     {
  13.         return w > y.w;//小到大
  14.     }
  15. };
  16. int n, m;
  17. priority_queue<node>q;
  18. vector<node> e[N];
  19. ll dis[N], vis[N];
  20. void Dij()
  21. {
  22.     dis[1] = 0;//从1号点出发，表示从1到1距离为0
  23.     q.push({ 1,dis[1] });//1号点以及到1的距离入队
  24.     while (q.size())
  25.     {
  26.         int u = q.top().v;//取最小边相连的点出队
  27.         q.pop();
  28.         if (vis[u])//访问过则跳过
  29.             continue;
  30.         vis[u] = 1;//没访问赋为访问
  31.         for (auto i : e[u])//遍历以u为出发点的边
  32.         {
  33.             int v = i.v, w = i.w;//取其相连的点及权值
  34.             if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
  35.             {
  36.                 dis[v] = dis[u] + w;
  37.                 q.push({ v,dis[v] });//v点以及到v的距离
  38.             }
  39.         }
  40.     }
  41.  
  42. }
  43. int main()
  44. {
  45.     cin >> n >> m;
  46.     fill(dis+1, dis+1+n, inf);//赋值一个无穷大，表示没有连接
  47.     for (int i = 1; i <= m; i++)
  48.     {
  49.         int x, y, w;
  50.         cin >> x >> y >> w;
  51.         e[x].push_back({ y,w });//存入以x出发到y，权值为w
  52.     }
  53.     Dij();
  54.     for (int i = 1; i <= n; i++)
  55.     {
  56.         if (dis[i] >= inf)//无法到达
  57.             cout << -1 << " ";
  58.         else
  59.             cout << dis[i] << " ";
  60.     }
  61. }

题目二（随机数据下的最短路径）： 

 

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
  8. struct  node
  9. {
  10.     ll v, w;
  11.     bool operator <(const node& y) const//重载一个<,用于优先队列排序
  12.     {
  13.         return w > y.w;//小到大
  14.     }
  15. };
  16. int n, m, t;
  17. priority_queue<node>q;
  18. vector<node> e[N];
  19. ll dis[N], vis[N];
  20. void Dij(int t)
  21. {
  22.     dis[t] = 0;//从t号点出发，表示从t到t距离为0
  23.     q.push({ t,dis[t] });//t号点以及到t的距离入队
  24.     while (q.size())
  25.     {
  26.         int u = q.top().v;//取最小边相连的点出队
  27.         q.pop();
  28.         if (vis[u])//访问过则跳过
  29.             continue;
  30.         vis[u] = 1;//没访问赋为访问
  31.         for (auto i : e[u])//遍历以u为出发点的边
  32.         {
  33.             int v = i.v, w = i.w;//取其相连的点及权值
  34.             if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
  35.             {
  36.                 dis[v] = dis[u] + w;
  37.                 q.push({ v,dis[v] });//v点以及到v的距离
  38.             }
  39.         }
  40.     }
  41.  
  42. }
  43. int main()
  44. {
  45.     cin >> n >> m>> t;
  46.     fill(dis+1, dis+1+n, inf);//赋值一个无穷大，表示没有连接
  47.     for (int i = 1; i <= m; i++)
  48.     {
  49.         int x, y, w;
  50.         cin >> x >> y >> w;
  51.         e[x].push_back({ y,w });//存入以x出发到y，权值为w
  52.     }
  53.     Dij(t);//从t点出发
  54.     for (int i = 1; i <= n; i++)
  55.     {
  56.         if (dis[i] == inf)//无法到达
  57.             cout << -1 << " ";
  58.         else
  59.             cout << dis[i] << " ";
  60.     }
  61. }

题目三（出差）：

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
  8. struct  node
  9. {
  10. 	int v, w;
  11. 	bool operator <(const node& y) const//重载一个<,用于优先队列排序
  12. 	{
  13. 		return w > y.w;//小到大
  14. 	}
  15. };
  16. int n, m;
  17. priority_queue<node>q;
  18. vector<node> e[N];
  19. int dis[N], vis[N], time0[N];
  20. void Dij()
  21. {
  22. 	dis[1] = 0;//从1号点出发，表示从1到1距离为0
  23. 	q.push({ 1,dis[1] });//1号点以及到1的距离入队
  24. 	while (q.size())
  25. 	{
  26. 		int u = q.top().v;//取最小边相连的点出队
  27. 		q.pop();
  28. 		if (vis[u])//访问过则跳过
  29. 			continue;
  30. 		vis[u] = 1;//没访问赋为访问
  31. 		for (auto i : e[u])//遍历以u为出发点的边
  32. 		{
  33. 			int v = i.v, w = i.w;//取其相连的点及权值
  34. 			if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
  35. 			{
  36. 				dis[v] = dis[u] + w;
  37. 				q.push({ v,dis[v] });//v点以及到v的距离
  38. 			}
  39. 		}
  40. 	}
  41. }
  42. int main()
  43. {
  44. 	cin >> n >> m;
  45. 	for (int i = 1; i <= n; i++)
  46. 		cin >> time0[i];
  47. 	fill(dis + 1, dis + 1 + n, inf);//赋值一个无穷大，表示没有连接
  48. 	for (int i = 1; i <= m; i++)
  49. 	{
  50. 		int x, y, w;
  51. 		cin >> x >> y >> w;
  52. 		e[x].push_back({ y,w + time0[y]});//存入以x出发到y，权值为w+隔离时间
  53. 		e[y].push_back({ x,w + time0[x] });//存入以y出发到y,权值为w+隔离时间
  54. 	}
  55. 	Dij();
  56. 	cout << dis[n] - time0[n];//要减掉最后终点的隔离时间
  57. }

题目四（聪明的猴子）：

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6. const int N = 1e3+20;
  7. int m, n;
  8. int a[N],f[N],x[N],y[N];
  9. struct edge
  10. {
  11.     int v1, v2;
  12.     double w;
  13. };
  14. vector<edge> e;
  15. int find(int k)//查找
  16. {
  17.     if (f[k] == k)
  18.         return k;
  19.     return f[k] = find(f[k]);
  20. }
  21. void  merge(int x, int y)//合并
  22. {
  23.   x=find(x),y=find(y);
  24.     if (x!= y)
  25.         f[x] = f[y];
  26. }
  27. bool cmp(edge a, edge b)
  28. {
  29.     return a.w < b.w;
  30. }
  31. int main()
  32. {
  33.     cin >> m;
  34.     for (int i = 1; i <= m; i++)
  35.         cin >> a[i];
  36.     cin >> n;
  37.     for (int j = 1; j <= n; j++)
  38.     {
  39.         cin >> x[j] >> y[j];
  40.         f[j] = j;//初始化并查集根
  41.     }
  42.     for(int i=1;i<=n;i++)
  43.         for (int j = i + 1; j <= n; j++)//添加边
  44.         {
  45.             double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
  46.             e.push_back({ i, j, w });
  47.         }
  48.     sort(e.begin(), e.end(), cmp);//边从小到大排序
  49.     double maxw = 0.0;//记录最小生成树中最大边
  50.     int cnt = 0;
  51.     for (int i = 0; i < e.size(); i++)
  52.     {
  53.         if (find(e[i].v1) != find(e[i].v2))//不属于一个集合
  54.         {
  55.             merge(e[i].v1, e[i].v2);//合并
  56.             cnt++;
  57.             maxw = max(maxw, e[i].w);//更新最小生成树中最大边
  58.         }
  59.         if (cnt == n-1)//n个点只需要n-1条边，选取n-1条边后，跳出循环
  60.             break;
  61.     }
  62.     int ans = 0;
  63.     for (int i = 1; i <= m; i++)
  64.     {
  65.         if (a[i] >= maxw)//有几只猴子大于最小生成树中最大边
  66.             ans++;
  67.     }
  68.     cout << ans;
  69. }

题目五（通电）：

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6. const int N = 1e3+20;
  7. int m, n;
  8. int h[N],f[N],x[N],y[N];
  9. struct edge
  10. {
  11.     int v1, v2;
  12.     double w;
  13. };
  14. vector<edge> e;
  15. int find(int k)//查找
  16. {
  17.     if (f[k] == k)
  18.         return k;
  19.     return f[k] = find(f[k]);
  20. }
  21. void  merge(int x, int y)//合并
  22. {
  23.   x=find(x),y=find(y);
  24.     if (x!= y)
  25.         f[x] = f[y];
  26. }
  27. bool cmp(edge a, edge b)
  28. {
  29.     return a.w < b.w;
  30. }
  31. int main()
  32. {
  33.     cin >> n;
  34.     for (int j = 1; j <= n; j++)
  35.     {
  36.         cin >> x[j] >> y[j]>> h[j];
  37.         f[j] = j;//初始化并查集根
  38.     }
  39.     for(int i=1;i<=n;i++)
  40.         for (int j = i + 1; j <= n; j++)//添加边
  41.         {
  42.             double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))+(h[i]-h[j])*(h[i]-h[j]);
  43.             e.push_back({ i, j, w });
  44.         }
  45.     sort(e.begin(), e.end(), cmp);//边从小到大排序
  46.     double maxw = 0.0;//记录最小生成树中最大边
  47.     double ans=0;
  48.     int cnt=0;
  49.     for (int i = 0; i < e.size(); i++)
  50.     {
  51.         if (find(e[i].v1) != find(e[i].v2))//不属于一个集合
  52.         {
  53.             merge(e[i].v1, e[i].v2);//合并
  54.             ans+=e[i].w;//求和
  55.             maxw = max(maxw, e[i].w);//更新最小生成树中最大边
  56.         }
  57.         if (cnt == n-1)//n个点只需要n-1条边，选取n-1条边后，跳出循环
  58.             break;
  59.     }
  60.     printf("%.2lf",ans);
  61. }

 题目六（机房）：

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll N = 3e5 + 10, M = 1e6 + 10;
  8. struct  node
  9. {
  10.     ll v, w;
  11.     bool operator <(const node& y) const//重载一个<,用于优先队列排序
  12.     {
  13.         return w > y.w;//小到大
  14.     }
  15. };
  16. int n, m;
  17. priority_queue<node>q;
  18. vector<node> e[N];
  19. vector<node> temp;
  20. ll dis[N], vis[N], cnt[N];
  21. ll Dij(int u, int end)
  22. {
  23.     memset(vis, 0, sizeof(vis));
  24.     memset(dis, 0x3f3f, sizeof(dis));
  25.     dis[u] = 0;//从u号点出发，表示从u到u距离为0
  26.     q.push({ u,dis[u] });//u号点以及到u的距离入队
  27.     while (q.size())
  28.     {
  29.         int u = q.top().v;//取最小边相连的点出队
  30.         q.pop();
  31.         if (vis[u])//访问过则跳过
  32.             continue;
  33.         vis[u] = 1;//没访问赋为访问
  34.         for (auto i : e[u])//遍历以u为出发点的边
  35.         {
  36.             int v = i.v, w = i.w;//取其相连的点及权值
  37.             if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
  38.             {
  39.                 dis[v] = dis[u] + w;
  40.                 q.push({ v,dis[v] });//v点以及到v的距离
  41.             }
  42.         }
  43.     }
  44.     return dis[end]+cnt[end];//还需要加上自身延迟
  45. }
  46. int main()
  47. {
  48.     cin >> n >> m;
  49.     for (int i = 1; i <= n - 1; i++)
  50.     {
  51.         int x, y;
  52.         cin >> x >> y;
  53.         cnt[x]++, cnt[y]++;
  54.         temp.push_back({ x,y });//临时存两个顶点
  55.     }
  56.     for (int i = 0; i < n - 1; i++)//根据度构造边
  57.     {
  58.         int u = temp[i].v, v = temp[i].w;
  59.         e[u].push_back({ v,cnt[u] });//u->v的边，权值为u的度
  60.         e[v].push_back({ u,cnt[v] });
  61.     }
  62.     while (m--)//m次查询
  63.     {
  64.         int u, v;
  65.         cin >> u >> v;
  66.         if (u == v)
  67.             cout << cnt[u] << endl;
  68.         else
  69.         {
  70.             ll ans = Dij(u, v);
  71.             cout << ans << endl;
  72.         }
  73.     }
  74. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/348670?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号