devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图论中的模板

作者：天景科技苑 | 2024-07-17 23:05:18

赞

踩

图论中的模板

有向图的拓扑排序

  1. //有向图无环图中才有拓扑排序，且都是前面的编号的点指向后面编号的点
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 1e5 + 9;
  6. int e[N], ne[N], h[N], idx, n, m, d[N], q[N];
  7.  
  8. void add(int a, int b)
  9. {
  10.     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
  11. }
  12.  
  13. bool topsort()
  14. {
  15.     int hh = 0, tt = -1;
  16.     //将所有入度为0的点入队，编号从1~n
  17.     for (int i = 1; i <= n; ++i) if (!d[i]) q[++tt] = i;
  18.  
  19.     while (hh <= tt)
  20.     {
  21.         int t = q[hh++];//出队
  22.         for (int i = h[t]; i != -1; i = ne[i])
  23.         {
  24.             int j = e[i];
  25.             d[j]--;//因为t指向j，又因为t删除了，所以j入度减一
  26.             if (!d[j]) q[++tt] = j;
  27.         }
  28.     }
  29.     return tt == (n - 1);//如果每个点都入队了表明为拓扑排序
  30. }
  31.  
  32. int main()
  33. {
  34.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  35.     memset(h, -1, sizeof h);
  36.     cin >> n >> m;
  37.     for (int i = 0; i < m; ++i)
  38.     {
  39.         int a, b; cin >> a >> b;
  40.         add(a, b);
  41.         d[b]++;//入度加一
  42.     }
  43.     //队列中的顺序刚好就是拓扑排序，排序不唯一
  44.     if (topsort()) for (int i = 0; i < n; ++i) cout << q[i] << " ";
  45.     else cout << -1;
  46.     return 0;
  47. }

dijkstra求最短路

  1. //dijkstra堆优化
  2. #include<iostream>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int N = 1e5 + 9;
  7. typedef pair<int, int> PII;
  8. int h[N], e[N], ne[N], idx, n, m, dist[N], w[N];
  9. bool st[N];
  10.  
  11. void add(int x, int y, int z)
  12. {
  13.     e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
  14. }
  15.  
  16. int dijkstra()
  17. {
  18.     memset(dist, 0x3f, sizeof dist);
  19.     dist[1] = 0;
  20.     //first是距离。second是编号
  21.     //小根堆
  22.     //有更改就加入
  23.     //可能加入的点会有冗余，比如1号点一个是10,一个是15，所以用一个st[]数组来标记
  24.     priority_queue<PII, vector<PII>, greater<PII>> heap;
  25.     heap.push({ 0, 1 });
  26.     while (heap.size())
  27.     {
  28.         //每次取出距离最小的点
  29.         auto t = heap.top();
  30.         heap.pop();
  31.         int ver = t.second, distance = t.first;
  32.         //不更新也对，不过会有很多冗余情况考虑
  33.         //同一个顶点x，可能在队列中有(dis1, x)、(dis2, x)存在
  34.         //而dis1 < dis2，所以(dis1, x)先出队并更新x的邻接顶点
  35.         //当(dis2, x)出队的时候，由于dis2 > dis1
  36.         //所以x的邻接顶点此时都不会更新，那么(dis2, x)这一步也就冗余了
  37.         if (st[ver]) continue;//如果距离已经确定，则跳过该点
  38.         st[ver] = true;
  39.         for (int i = h[ver]; i != -1; i = ne[i])
  40.         {
  41.             int j = e[i];
  42.             if (dist[j] > distance + w[i])
  43.             {
  44.                 dist[j] = distance + w[i];
  45.                 heap.push({ dist[j], j });
  46.             }
  47.         }
  48.     }
  49.     if (dist[n] == 0x3f3f3f3f) return -1;
  50.     return dist[n];
  51. }
  52.  
  53. int main()
  54. {
  55.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  56.     memset(h, -1, sizeof h);
  57.     cin >> n >> m;
  58.  
  59.     while (m--)
  60.     {
  61.         int x, y, z; cin >> x >> y >> z;
  62.         add(x, y, z);
  63.     }
  64.     cout << dijkstra();
  65.     return 0;
  66. }

有边数限制的最短路

  1. //bellman_ford()算法
  2. //dijkstra()不能解决负权边最短路问题
  3. #include<iostream>
  4. #include<cstring>
  5. using namespace std;
  6. const int N = 510, M = 1e4 + 9;
  7. //back[]存储上一次的dist[]
  8. int dist[N], back[N], n, m, k;
  9.  
  10. struct Edge
  11. {
  12.     int a, b, w;
  13. } edges[M];
  14.  
  15. int  bellman_ford()
  16. {
  17.     memset(dist, 0x3f, sizeof dist);
  18.     dist[1] = 0;
  19.     //存在边数限制，只能用bellman_ford做
  20.     //关于为什么循环k次可以保证得到的dist就是相应k条件下的值？
  21.     //当明白了备份的作用，就能理解了
  22.     //备份的意义就是保证了每条边a->b在每次刷新时a都是独立的
  23.     //在遍历过程中dist不会受其他点的影响，只和a上一次的值有关
  24.     //而这个备份的操作就是放在k循环下的，所以得到的dist就是相应k条件下的值
  25.     for (int i = 0; i < k; ++i)
  26.     {
  27.         //做备份
  28.         //防止发生串联
  29.         //串联：由于这个算法的特性决定，
  30.         //每次更新得到的必然是在多考虑 1 条边之后能得到的全局的最短路
  31.         //而串联指的是一次更新之后考虑了不止一条边：由于使用了松弛
  32.         //某节点的当前最短路依赖于其所有入度的节点的最短路
  33.         //假如在代码中使用dist[e.b]=min(dist[e.b],dist[e.a] + e.c)
  34.         //我们无法保证dist[e.a]是否也在本次循环中被更新，如果被更新了
  35.         //并且dist[e.b] > dist[e.a] + e.c
  36.         //那么会造成当前节点在事实上“即考虑了一条从某个节点指向a的边
  37.         //也考虑了a->b”，共两条边
  38.         //而使用dist[e.b]=min(dist[e.b],last[e.a] + e.c)
  39.         //可以保证a在dist更新后不影响对b的判定，因为后者使用last数组
  40.         //保存着上一次循环中的dist的值
  41.         memcpy(back, dist, sizeof dist);
  42.         for (int j = 0; j < m; ++j)
  43.         {
  44.             int a = edges[j].a, b = edges[j].b, w = edges[j].w;
  45.             dist[b] = min(dist[b], back[a] + w);
  46.         }
  47.     }
  48.     //因为可能存在到n的路径中有负权边存在， 所以导致dist[n]的值小于0x3f3f3f3f
  49.     //根据题目给的数据范围最多减去500*10000，也就是500w的值，所以大于一半就好
  50.     //注意不要返回-1，因为-1可能就是dist[n]的距离
  51.     if (dist[n] > 0x3f3f3f3f >> 1) return -0x3f3f3f3f;
  52.     return dist[n];
  53. }
  54.  
  55. int main()
  56. {
  57.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  58.     cin >> n >> m >> k;
  59.  
  60.     for (int i = 0; i < m; ++i)
  61.     {
  62.         int x, y, z; cin >> x >> y >> z;
  63.         edges[i].a = x, edges[i].b = y, edges[i].w = z;
  64.     }
  65.     int t = bellman_ford();
  66.     if (t == -0x3f3f3f3f) cout << "impossible";
  67.     else cout << dist[n];
  68.     return 0;
  69. }

spfa求最短路

  1. //spfa
  2. #include<iostream>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int N = 1e5 + 9;
  7. int h[N], e[N], ne[N], st[N], n, m, idx, w[N], dist[N];
  8.  
  9. void add(int a, int b, int c)
  10. {
  11.     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
  12. }
  13.  
  14. int spfa()
  15. {
  16.     memset(dist, 0x3f, sizeof dist);
  17.     dist[1] = 0;
  18.     queue<int> q;//存储待更新点
  19.     q.push(1);
  20.     st[1] = true;
  21.  
  22.     while (q.size())
  23.     {
  24.         auto t = q.front();
  25.         q.pop();
  26.         st[t] = false;
  27.  
  28.         for (int i = h[t]; i != -1; i = ne[i])
  29.         {
  30.             int j = e[i];
  31.             if (dist[j] > dist[t] + w[i])
  32.             {
  33.                 dist[j] = dist[t] + w[i];
  34.                 if (!st[j])
  35.                 {
  36.                     q.push(j);
  37.                     st[j] = true;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     if (dist[n] == 0x3f3f3f3f) return -0x3f3f3f3f;
  43.     return dist[n];
  44. }
  45.  
  46. int main()
  47. {
  48.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  49.     memset(h, -1, sizeof h);
  50.     cin >> n >> m;
  51.     while (m--)
  52.     {
  53.         int x, y, z; cin >> x >> y >> z;
  54.         add(x, y, z);
  55.     }
  56.  
  57.     int t = spfa();
  58.     if (t == -0x3f3f3f3f) cout << "impossible";
  59.     else cout << t;
  60.     return 0;
  61. }

spfa判负环

  1. //spfa判断负环
  2. #include<iostream>
  3. #include<queue>
  4. #include<cstring>
  5. using namespace std;
  6. const int N = 1e4 + 9;
  7. //cnt[]存储点最短路径的边数
  8. int e[N], ne[N], h[N], w[N], dist[N], cnt[N], idx, n, m;
  9.  
  10. void add(int a, int b, int c)
  11. {
  12.     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
  13. }
  14.  
  15. bool spfa()
  16. {
  17.     memset(dist, 0x3f, sizeof dist);
  18.     queue<int> q;
  19.     //注意这里是讲所有点都入队，因为负环可能不在1号点这个路径上
  20.     //这里dist初不初始化都行，但要是求单点到单点路径上是否存在回路，必须初始化dist
  21.     //且dist[s] = 0
  22.     for (int i = 1; i <= n; ++i) q.push(i);
  23.  
  24.     while (q.size())
  25.     {
  26.         auto t = q.front();
  27.         q.pop();
  28.  
  29.         for (int i = h[t]; i != -1; i = ne[i])
  30.         {
  31.             int j = e[i];
  32.             if (dist[j] > dist[t] + w[i])
  33.             {
  34.                 dist[j] = dist[t] + w[i];
  35.                 cnt[j] = cnt[t] + 1;
  36.                 //边数 >= n，点数 >= n + 1，存在回路
  37.                 if (cnt[j] >= n) return true;
  38.                 q.push(j);
  39.             }
  40.         }
  41.     }
  42.     return false;
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  48.     memset(h, -1, sizeof h);
  49.     cin >> n >> m;
  50.     while (m--)
  51.     {
  52.         int x, y, z; cin >> x >> y >> z;
  53.         add(x, y, z);
  54.     }
  55.     if (spfa()) cout << "Yes";
  56.     else cout << "No";
  57.     return 0;
  58. }

多源汇最短路问题-具有多个源点：Floyd求最短路

  1. //Floyd求多源汇最短路
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 210, INF = 1e9;
  6. int n, m, Q, d[N][N];
  7.  
  8. void floyd()
  9. {
  10.     for (int k = 1; k <= n; ++k)
  11.     {
  12.         for (int i = 1; i <= n; ++i)
  13.         {
  14.             for (int j = 1; j <= n; ++j)
  15.             {
  16.                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  17.             }
  18.         }
  19.     }
  20. }
  21.  
  22. int main()
  23. {
  24.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  25.     cin >> n >> m >> Q;
  26.     for (int i = 1; i <= n; ++i)
  27.     {
  28.         for (int j = 1; j <= n; ++j)
  29.         {
  30.             if (i == j) d[i][j] = 0;
  31.             else d[i][j] = INF;
  32.         }
  33.     }
  34.  
  35.     while (m--)
  36.     {
  37.         int a, b, z; cin >> a >> b >> z;
  38.         d[a][b] = min(d[a][b], z);//选一个最短的重边
  39.     }
  40.  
  41.     floyd();
  42.  
  43.     while (Q--)
  44.     {
  45.         int a, b; cin >> a >> b;
  46.         //因为存在负权边，所以ab之间的距离可能小于无穷
  47.         if (d[a][b] > INF / 2) cout << "impossible" << '\n';
  48.         else cout << d[a][b] << '\n';
  49.     }
  50.  
  51.     return 0;
  52. }

Kruskal算法求最小生成树

  1. //kruskal求最小生成树
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 2e5 + 9;
  6.  
  7. struct Edge
  8. {
  9.     int a, b, w;
  10.     bool operator< (const Edge& W) const
  11.     {
  12.         return w < W.w;
  13.     }
  14. } edges[N];
  15.  
  16. int n, m, p[N], res, cnt;
  17.  
  18. int find(int x)
  19. {
  20.     if (p[x] != x) p[x] = find(p[x]);
  21.     return p[x];
  22. }
  23.  
  24. int main()
  25. {
  26.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  27.     cin >> n >> m;
  28.  
  29.     for (int i = 0; i < m; ++i)
  30.     {
  31.         int a, b, w; cin >> a >> b >> w;
  32.         edges[i] = { a, b, w };
  33.     }
  34.     //从小到大排序
  35.     sort(edges, edges + m);
  36.     //并查集数组初始化
  37.     for (int i = 1; i <= n; ++i) p[i] = i;
  38.     //如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。
  39.     //判断是否会产生回路的方法为：使用并查集。
  40.     //每次将未加入的边加入到集合中去
  41.     for (int i = 0; i < m; ++i)
  42.     {
  43.         int a = edges[i].a, b = edges[i].b, w = edges[i].w;
  44.         //不在一个集合里面
  45.         a = find(a), b = find(b);
  46.         if (a != b)
  47.         {
  48.             res += w;
  49.             cnt++;
  50.             p[a] = b;//加入集合
  51.         }
  52.     }
  53.     //如果集合中的边数小于n - 1，说明不存在最小生成树
  54.     if (cnt < n - 1) cout << "impossible";
  55.     else cout << res;
  56.     return 0;
  57. }

判定是否是二分图

  1. #include<iostream>
  2. #include<cstring>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 100010;
  7.  
  8. int f[N];
  9. int e[N*2],h[N],ne[N*2],idx;
  10. //数组模拟邻接表模板
  11. void add(int a,int b)
  12. {
  13.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
  14. }
  15. //并查集find函数模板：找到祖宗节点
  16. int find(int x)
  17. {
  18.     if(f[x]!=x) f[x]=find(f[x]);
  19.     return f[x];
  20. }
  21.  
  22. int main()
  23. {
  24.     int n,m;
  25.     scanf("%d%d",&n,&m);
  26.     memset(h,-1,sizeof h);
  27.     //并查集初始化
  28.     for(int i=1;i<=n;i++) f[i]=i;
  29.     while(m--)
  30.     {
  31.         int a,b;
  32.         scanf("%d%d",&a,&b);
  33.         add(a,b);
  34.         add(b,a);
  35.     }
  36.     //遍历每一个点
  37.     for(int u=1;u<=n;u++)
  38.     {
  39.         //遍历当前点的邻接点
  40.         for(int i=h[u];~i;i=ne[i])
  41.         {
  42.             int j=e[i];
  43.             //如果邻接点和当前节点属于同一集合，不满足二分，直接NO
  44.             if(find(j)==find(u))
  45.             {
  46.                 puts("No");
  47.                 return 0;
  48.             }
  49.             //将所有邻接点合并到同一个集合
  50.             f[find(e[h[u]])]=find(j);
  51.         }
  52.     }
  53.     puts("Yes");
  54.     return 0;
  55. }

二分图的最大匹配

  1. //二分图的最大匹配
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 510, M = 1e5 + 9;
  6. int h[N], e[M], ne[M], n1, n2, match[N], m, idx, res;
  7. bool st[N];
  8.  
  9. void add(int a, int b)
  10. {
  11.     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
  12. }
  13.  
  14. bool find(int x)
  15. {
  16.     for (int i = h[x]; i != -1; i = ne[i])
  17.     {
  18.         int j = e[i];
  19.         //没被遍历过
  20.         if (!st[j])
  21.         {
  22.             //标记为匹配过
  23.             st[j] = true;
  24.             //如果这个姑娘还没有被匹配过，或者找到这个男生喜欢别的姑娘
  25.             if (match[j] == 0 || find(match[j]))
  26.             {
  27.                 match[j] = x;
  28.                 return true;
  29.             }
  30.         }
  31.     }
  32.     return false;
  33. }
  34.  
  35. int main()
  36. {
  37.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  38.     memset(h, -1, sizeof h);
  39.  
  40.     cin >> n1 >> n2 >> m;
  41.  
  42.     while (m--)
  43.     {
  44.         int a, b; cin >> a >> b;
  45.         //不需要存双向边
  46.         add(a, b);
  47.     }
  48.  
  49.     for (int i = 1; i <= n1; ++i)
  50.     {
  51.         //每次将姑娘全初始化为没有遍历，因为之前别人喜欢的姑娘我也可能喜欢
  52.         memset(st, false, sizeof st);
  53.         if (find(i)) res++;//如果找到数量就加一
  54.     }
  55.     cout << res;
  56.     return 0;
  57. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/842435
推荐阅读
相关标签

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

  

闽ICP备14008679号