图论方法应用 小鱼儿 2022-10-17 00:54 154阅读 0赞 ### 声明：本博客题目和题解均来自www.acwing.com，侵权联删。 ### 各种图论题目最合适的解法如下： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01lbmdZaUtlTmFu_size_16_color_FFFFFF_t_70] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01lbmdZaUtlTmFu_size_16_color_FFFFFF_t_70 1] ### 1. Dijkstra求最短路（朴素法） ### 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n n n 号点的最短距离，如果无法从 1 号点走到 n n n 号点，则输出 −1 。 **输入格式** 第一行包含整数 n n n 和 m m m。 接下来 m m m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 **输出格式** 输出一个整数，表示 1号点到 n n n号点的最短距离。 如果路径不存在，则输出 −1。 **数据范围** 1 ≤ n ≤ 500 , 1≤n≤500, 1≤n≤500, 1 ≤ m ≤ 1 0 5 , 1≤m≤10^5, 1≤m≤105, 图中涉及边长均不超过10000。 **输入样例：** 3 3 1 2 2 2 3 1 1 3 4 **输出样例：** 3 **标程：** #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N = 510; int g[N][N]; int dist[N]; bool st[N]; int n,m; int dijkstra() { memset(dist,0x3f,sizeof dist); dist[1] = 0; for(int i = 1; i < n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!st[j] && (t == -1 || dist[j] < dist[t])){ t = j; } } for(int j = 1; j <= n; j++){ dist[j] = min(dist[j],dist[t]+g[t][j]); } st[t] = true; } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { memset(g,0x3f,sizeof g); scanf("%d%d",&n,&m); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b] = min(g[a][b],c); } printf("%d",dijkstra()); return 0; } ### 2. Dijkstra求最短路（堆优化版） ### 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。 请你求出 1 号点到 n n n 号点的最短距离，如果无法从 1 号点走到 n n n 号点，则输出 −1 。 **输入格式** 第一行包含整数 n n n 和 m m m。 接下来 m m m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 **输出格式** 输出一个整数，表示 1号点到 n n n号点的最短距离。 如果路径不存在，则输出 −1。 **数据范围** 1 ≤ n , m ≤ 1.5 × 1 0 5 , 1≤n,m≤1.5×10^5 , 1≤n,m≤1.5×105, 图中涉及边长均不小于 0，且不超过 10000。 **输入样例：** 3 3 1 2 2 2 3 1 1 3 4 **输出样例：** 3 **标程：** #include<iostream> #include<queue> #include<cstring> #include<cstdio> #include<vector> using namespace std; typedef pair<int ,int> pii; const int N = 150010; int h[N],e[N],ne[N],w[N],idx; int dist[N]; bool st[N]; int n,m; void add(int a,int b,int c){ e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int dijkstra() { memset(dist,0x3f,sizeof dist); dist[1] = 0; priority_queue<pii,vector<pii>,greater<pii>> heap; heap.push({ 0,1}); while(heap.size()){ pii t = heap.top(); heap.pop(); int ver = t.second; if(st[ver]) continue; st[ver] = true; for(int i = h[ver]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > dist[ver] + w[i]){ dist[j] = dist[ver] + w[i]; heap.push({ dist[j],j}); } } } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } printf("%d",dijkstra()); return 0; } ### 3. 有边数限制的最短路 （bellman-ford） ### 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环， **边权可能为负数**。 请你求出从 1 1 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，输出 `impossible`。 注意：图中可能 **存在负权回路** 。 **输入格式** 第一行包含三个整数 n , m , k n,m,k n,m,k 。 接下来 m m m 行，每行包含三个整数 x , y , z x,y,z x,y,z，表示存在一条从点 x x x 到点 y y y 的有向边，边长为 z z z。 **输出格式** 输出一个整数，表示从 1 1 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离。 如果不存在满足条件的路径，则输出 `impossible`。 **数据范围** 1 ≤ n , k ≤ 500 , 1≤n,k≤500, 1≤n,k≤500, 1 ≤ m ≤ 10000 , 1≤m≤10000, 1≤m≤10000, 任意边长的绝对值不超过 10000 10000 10000。 **输入样例：** 3 3 1 1 2 1 2 3 1 1 3 3 **输出样例：** 3 **标程：** #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 510,M = 1e4+10; struct Edge { int a,b,c; }edges[M]; int n,m,k; int dist[N],last[N]; void bellman_ford() { memset(dist,0x3f,sizeof dist); dist[1] = 0; for(int i = 0; i < k; i++){ memcpy(last,dist,sizeof dist); for(int j = 0; j < m; j++){ auto e = edges[j]; dist[e.b] = min(dist[e.b],last[e.a]+e.c); } } } int main() { cin >> n >> m >> k; for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); edges[i] = { a,b,c}; } bellman_ford(); if(dist[n] > 0x3f3f3f3f/2) puts("impossible"); else printf("%d\n",dist[n]); return 0; } ### 4. spfa求最短路 ### 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环， **边权可能为负数**。 请你求出 1 1 1 号点到 n n n 号点的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，则输出 `impossible`。 数据保证不存在负权回路。 **输入格式** 第一行包含三个整数 n , m n,m n,m 。 接下来 m m m 行，每行包含三个整数 x , y , z x,y,z x,y,z，表示存在一条从点 x x x 到点 y y y 的有向边，边长为 z z z。 **输出格式** 输出一个整数，表示 1 1 1 号点到 n n n 号点的最短距离。 如果路径不存在，则输出 `impossible`。 **数据范围** 1 ≤ n , m ≤ 1 0 5 , 1≤n,m≤10^5, 1≤n,m≤105, 图中涉及边长绝对值均不超过 10000 10000 10000。 **输入样例：** 3 3 1 2 5 2 3 -3 1 3 4 **输出样例：** 2 #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int N = 1e5+10; int n,m; int h[N],w[N],e[N],ne[N],idx; int dist[N]; bool st[N]; void add(int a,int b,int c){ e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int spfa() { memset(dist,0x3f,sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while(!q.empty()){ int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > dist[t]+w[i]){ dist[j] = dist[t] + w[i]; if(!st[j]){ st[j] = true; q.push(j); } } } } return dist[n]; } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } int t = spfa(); if(t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n",t); return 0; } ### 5. spfa判断负环 ### 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环， **边权可能为负数**。 请你判断图中是否存在负权回路。 **输入格式** 第一行包含整数 n n n 和 m m m。 接下来 m m m 行每行包含三个整数 x , y , z x,y,z x,y,z，表示存在一条从点 x x x 到点 y y y 的有向边，边长为 z z z。 **输出格式** 如果图中存在负权回路，则输出 `Yes`，否则输出 `No`。 **数据范围** 1 ≤ n ≤ 2000 , 1≤n≤2000, 1≤n≤2000, 1 ≤ m ≤ 10000 , 1≤m≤10000, 1≤m≤10000, 图中涉及边长绝对值均不超过 10000 10000 10000。 **输入样例：** 3 3 1 2 -1 2 3 4 3 1 -4 **输出样例：** Yes **标程：** #include<iostream> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int N = 2e3+10,M = 1e4+10; int n,m; int h[N],e[M],w[M],ne[M],idx; int dist[N],cnt[N]; bool st[N]; void add(int a,int b,int c){ e[idx] = b; w[idx] = c; ne[idx] =h[a]; h[a] = idx++; } bool spfa(){ queue<int> q; for(int i = 1; i <= n; i++){ q.push(i); st[i] = true; } while(q.size()){ int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > dist[t] + w[i]){ dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if(cnt[j] >= n) return true; if(!st[j]){ st[j] = true; q.push(j); } } } } return false; } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } if(spfa()) puts("Yes"); else puts("No"); return 0; } ### 6. Floyd求最短路 ### 给定一个 n 个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定 k个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y的最短距离，如果路径不存在，则输出 impossible。 数据保证图中不存在负权回路。 **输入格式** 第一行包含三个整数 n,m,k。 接下来 m行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 接下来 k行，每行包含两个整数 x,y，表示询问点 x 到点 y的最短距离。 **输出格式** 共 k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 `impossible`。 **数据范围** 1 ≤ n ≤ 200 , 1≤n≤200, 1≤n≤200, 1 ≤ k ≤ n 2 1≤k≤n^2 1≤k≤n2 1 ≤ m ≤ 20000 , 1≤m≤20000, 1≤m≤20000, 图中涉及边长绝对值均不超过 10000 10000 10000。 **输入样例：** 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3 **输出样例：** impossible 1 **标程：** #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 210,INF = 1e9; int n,m,t; int g[N][N]; void floyd() { for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ g[i][j] = min(g[i][j],g[i][k]+g[k][j]); } } } } int main() { scanf("%d%d%d",&n,&m,&t); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i == j) g[i][j] = 0; else g[i][j] = INF; } } for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b] = min(g[a][b],c); } floyd(); for(int i = 0; i < t; i++){ int a,b; scanf("%d%d",&a,&b); if(g[a][b] > INF/2) puts("impossible"); else printf("%d\n",g[a][b]); } return 0; } ### 7. Prim算法求最小生成树 ### 给定一个 n n n个点 m m m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 `impossible`。 给定一张边带权的无向图 G = ( V , E ) G=(V,E) G=(V,E)，其中 V V V 表示图中点的集合， E E E 表示图中边的集合， n = ∣ V ∣ ， m = ∣ E ∣ n=|V|，m=|E| n=∣V∣，m=∣E∣。 由 V V V 中的全部 n n n 个顶点和 E E E 中 n − 1 n−1 n−1 条边构成的无向连通子图被称为 G G G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G G G 的最小生成树。 **输入格式** 第一行包含两个整数 n n n 和 m m m。 接下来 m行，每行包含三个整数 u , v , w u,v,w u,v,w，表示点 u u u 和点 v v v 之间存在一条权值为 w w w 的边。 **输出格式** 共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 `impossible`。 **数据范围** 1 ≤ n ≤ 500 , 1≤n≤500, 1≤n≤500, 1 ≤ m ≤ 105 , 1≤m≤105, 1≤m≤105, 图中涉及边的边权的绝对值均不超过 10000 10000 10000。 **输入样例：** 4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4 **输出样例：** 6 **标程：** #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N = 510,INF = 0x3f3f3f3f; int n,m; int g[N][N]; int dist[N]; bool st[N]; int prime() { memset(dist,0x3f,sizeof dist); int ans = 0; for(int i = 0; i < n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; } if(i && dist[t] == INF) return INF; if(i) ans += dist[t]; st[t] = true; for(int j = 1; j <= n; j++) dist[j] = min(dist[j],g[t][j]); } return ans; } int main() { scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b] = g[b][a] = min(g[a][b],c); } int t = prime(); if(t == INF) printf("impossible\n"); else printf("%d\n",t); } ### 8. Kruskal算法求最小生成树 ### 给定一个 n n n 个点 m m m条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 `impossible`。 给定一张边带权的无向图 G = ( V , E ) G=(V,E) G=(V,E)，其中 V V V 表示图中点的集合， E E E 表示图中边的集合， n = ∣ V ∣ ， m = ∣ E ∣ n=|V|，m=|E| n=∣V∣，m=∣E∣。 由 V V V 中的全部 n n n 个顶点和 E E E 中 n − 1 n−1 n−1 条边构成的无向连通子图被称为 G G G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G G G 的最小生成树。 **输入格式** 第一行包含两个整数 n n n 和 m m m。 接下来 m m m 行，每行包含三个整数 u , v , w u,v,w u,v,w，表示点 u u u 和点 v v v 之间存在一条权值为 w w w 的边。 **输出格式** 共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 `impossible`。 **数据范围** 1 ≤ n ≤ 1 0 5 , 1≤n≤10^5, 1≤n≤105, 1 ≤ m ≤ 2 ∗ 1 0 5 , 1≤m≤2∗10^5, 1≤m≤2∗105, 图中涉及边的边权的绝对值均不超过 1000。 **输入样例：** 4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4 **输出样例：** 6 **标程：** #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N = 1e5+10,INF = 0x3f3f3f3f; struct Edge{ int a,b,w; bool operator<(const Edge &W) const{ return w < W.w; } }edges[N*2]; int n,m; int p[N]; int find(int x){ if(x != p[x]) return p[x] = find(p[x]); else return p[x]; } int kruskal() { sort(edges,edges+m); for(int i = 1; i <= n; i++) p[i] = i; int ans = 0,cnt = 0; for(int i = 0; i < m; i++){ int a = edges[i].a,b = edges[i].b,w = edges[i].w; a = find(a),b = find(b); if(a != b){ p[a] = b; ans += w; cnt++; } } if(cnt < n-1) return INF; else return ans; } int main() { scanf("%d%d",&n,&m); for(int i = 0 ; i< m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); edges[i] = { a,b,c}; } int t = kruskal(); if(t == INF) puts("impossible"); else printf("%d\n",t); } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01lbmdZaUtlTmFu_size_16_color_FFFFFF_t_70]: /images/20221014/518655f74b034ecf95982fdad4b522fd.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01lbmdZaUtlTmFu_size_16_color_FFFFFF_t_70 1]: /images/20221014/061aa222b9f94f859920d567567d7112.png
相关 图论小总结 图论最重要的就是怎么建图 在建图的时候主要考虑三件事情： 1.确定结点和边权 2.是否建分层图（最短路DP）？ 3.是否建拆点图（DP思想）？如果有限制条件，考虑两种情 系统管理员/ 2024年03月24日 14:11/ 0 赞/ 90 阅读
相关 图论 一、图的常用概念 1、顶点（vertex） 2、边（edge） 3、路径 4、无向图：顶点之间的连接没有方向 ![1007094-201909 柔光的暖阳◎/ 2023年10月10日 07:53/ 0 赞/ 76 阅读
相关 论软件设计方法及其应用 摘要： 2020年3月，本人就职的某互联网公司承担了“XXAPP电子商务系统”的开发，该项目是集团为用户提供电子商务业务，拉新促活，提高交易效率的重点项目，主要实现消费者的网 小灰灰/ 2023年10月09日 13:35/ 0 赞/ 55 阅读
相关 图论基础 图 图由节点和图构成； 有向图：连线有方向；不对称性； 无向图：连线无方向；是有向图的一种特殊请情况； 有权图：连线有权值； 无权图：连线无权值； 简 柔情只为你懂/ 2023年08月17日 17:48/ 0 赞/ 154 阅读
相关 图论之欧拉图 欧拉路径/欧拉回路 欧拉路径是一条经过图中所有边且只经过一次的路径（类似于一笔画问题）； 欧拉回路的话就是起点和终点相同的欧拉路径 欧拉通路（欧拉路径）：S点到T点的 蔚落/ 2023年08月17日 16:26/ 0 赞/ 167 阅读
相关 图论方法应用 声明：本博客题目和题解均来自www.acwing.com，侵权联删。 各种图论题目最合适的解法如下： ![在这里插入图片描述][watermark_type_ZmFu 小鱼儿/ 2022年10月17日 00:54/ 0 赞/ 155 阅读
相关 图论 http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_articl 清疚/ 2022年09月25日 15:21/ 0 赞/ 259 阅读
相关 图论算法 Problem1一笔画问题 题目描述 给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’ 输入 输入的第一 妖狐艹你老母/ 2022年01月06日 22:13/ 0 赞/ 271 阅读
相关 图论 Floyd算法 Floyd算法 时间复杂度O (n^3) 空间复杂度O (n^2) 用处 可以求任意两个点之间的最短路径长度。 得出的邻接矩阵存储 i 到 j 的 青旅半醒/ 2021年12月15日 05:01/ 0 赞/ 270 阅读
相关 图论重点复习 一、重点概念 1、图：一个图是一个序偶（V，E），记为G=( V , E),其中： （1） V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点 冷不防/ 2021年09月26日 18:36/ 0 赞/ 1136 阅读
系统管理员
柔光的暖阳◎
小灰灰
柔情只为你懂
小鱼儿
还没有评论，来说两句吧...