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

    目录

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

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

    题目一（蓝桥王国）：

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

    题目三（出差）：

    题目四（聪明的猴子）：

     题目六（机房）：

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

    1. #include
    2. #include
    3. #include
    4. #include
    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_queueq;
    18. vector 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
    2. #include
    3. #include
    4. #include
    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 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.     cin>>m;
    40.         for (int j = 1; j <= m; j++)//添加边
    41.         {
    42.             int v1,v2,w;
    43.             cin>>v1>>v2>>w;
    44.             e.push_back({ v1, v2, w });
    45.         }
    46.     sort(e.begin(), e.end(), cmp);//边从小到大排序
    47.     int cnt=0;
    48.     for (int i = 0; i < e.size(); i++)
    49.     {
    50.         if (find(e[i].v1) != find(e[i].v2))//不属于一个集合
    51.         {
    52.             merge(e[i].v1, e[i].v2);//合并
    53.         }
    54.         if (cnt == n-1)//n个点只需要n-1条边，选取n-1条边后，跳出循环
    55.             break;
    56.     }
    57. }

    题目一（蓝桥王国）：

    1. #include
    2. #include
    3. #include
    4. #include
    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_queueq;
    18. vector 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
    2. #include
    3. #include
    4. #include
    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_queueq;
    18. vector 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
    2. #include
    3. #include
    4. #include
    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_queueq;
    18. vector 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
    2. #include
    3. #include
    4. #include
    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 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
    2. #include
    3. #include
    4. #include
    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 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
    2. #include
    3. #include
    4. #include
    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_queueq;
    18. vector e[N];
    19. vector 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. }

  • 相关阅读:
    小白立创机械狗从零到成品总结
    Windows环境安装dmPython（WHL方式）
    vector中的迭代器失效问题
    数字孪生智慧场馆｜智慧协同，立体可控，节省方案智能化建设投资
    接近3w详解Docker搭建Redis集群（主从容错、主从扩容、主从缩容）
    JAVA中常用序列化与反序列化合集
    Linux下Nginx的安装和配置
    Python实现EasyOCR对图片的自动识别，并提取目标数据
    110道 MySQL面试题及答案 （持续更新）
    数仓开发之DWD层（二）
  • 原文地址：https://blog.csdn.net/qq_74156152/article/details/136666572