当前位置： 首页 > news >正文

保研考研机试攻略：第七章——图论（2）

news 来源：原创 2024/9/20 15:29:18

🍦🍦🍦今天我们继续来看图论的第二部分内容：最小生成树问题、最短路径问题、拓扑排序等内容。我们一起继续加油鸭~fighting！( •̀ ω •́ )✧

目录

🧊🧊🧊7.4 最小生成树问题

🥥例题：DreamJudge 1312

kruskal：

prim：

🥥练习题目：

DreamJudge 1311 继续畅通工程

DreamJudge 1341 还是畅通工程

DreamJudge 1183 Freckles 🍩

DreamJudge 1234 Jungle Roads 🍩

🧊🧊🧊7.5 最短路径问题

单源最短路径算法的选择：

🥥例题：DreamJudge 1565

 spfa：

floyd：

dijkstra：

C语言模板：

spfa：

🥥练习题目：

DreamJudge 1344 最短路径问题

DreamJudge 1286 最短路径

DreamJudge 1224 I Wanna Go Home 🍰

🧊🧊🧊7.6 拓扑排序

🥥例题：DreamJudge 1566

🧊🧊🧊7.4 最小生成树问题

几乎 99%的最小生成树问题都可以用 kruskal 算法解决，废话不多说，下面我们用例题来看看 kruskal 和 prim 两种算法的通用模板：

🥥例题：DreamJudge 1312

kruskal：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
struct node {int u, v, w;
}edge[maxn * maxn];
int cmp(node A, node B) {return A.w < B.w;
}
int fa[maxn];
int find(int x) {if (x == fa[x]) return x;fa[x] = find(fa[x]);return fa[x];
}
int main(){int N , M;while(scanf("%d%d",&M,&N) != EOF){if (M == 0) break;for (int i = 0; i < M; i++) {scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);}for (int i = 1; i <= N; i++) fa[i] = i;sort(edge, edge + M, cmp);int sum = 0;int total = 0;for (int i = 0; i < M; i++) {int fx = find(edge[i].u);int fy = find(edge[i].v);if (fx != fy) {fa[fx] = fy;sum += edge[i].w;total++;//统计加入边数量}}if (total < N - 1)//不能生成树printf("?\n");else printf("%d\n", sum);}return 0;
}

prim：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int mpt[maxn][maxn];//邻接矩阵存储图
int dist[maxn];
int main(){int N , M;while(scanf("%d%d",&M,&N) != EOF) {if (M == 0) break;for (int i = 1; i <= N; i++) {dist[i] = INF;//初始化为无穷大for (int j = 1; j <= N; j++) {if (i == j) mpt[i][j] = 0;else mpt[i][j] = INF;}}for(int i = 0;i < M;i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);mpt[u][v] = min(mpt[u][v], w);//防止重边mpt[v][u] = min(mpt[v][u], w);//重边用最小的}int sum = 0;int flag = 0;for (int i = 1; i <= N; i++) dist[i] = mpt[1][i];for (int i = 1; i < N; i++) {int min_len = INF;int min_p = -1;for (int j = 1; j <= N; j++) {if (min_len > dist[j] && dist[j] != 0) {min_len = dist[j];min_p = j;}}if (min_p == -1) {flag = 1; break;//判断是否能生成树}sum += min_len;for (int j = 1; j <= N; j++) {if (dist[j] > mpt[min_p][j] && dist[j] != 0)dist[j] = mpt[min_p][j];}}if (flag) printf("?\n");//不能生成树else printf("%d\n", sum);}return 0;
}

🥥练习题目：

DreamJudge 1311 继续畅通工程 

#include<bits/stdc++.h>
using namespace std;
const int maxm=105;
struct node{int u,v,w,state;
}edge[maxm*maxm];
bool cmp(node a,node b){if(a.state!=b.state) return a.state>b.state;//一定注意这一句，不然会错误return a.w<b.w;
}
int fa[maxm];
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int main()
{int n;while(cin>>n){if(n==0) break;int nn=n*(n-1)/2;for(int i=0;i<nn;i++) cin>>edge[i].u>>edge[i].v>>edge[i].w>>edge[i].state;for(int i=1;i<=n;i++) fa[i]=i;//再一个要注意的点就是这里顶点是从1~nsort(edge,edge+nn,cmp);int sum=0,total=0;for(int i=0;i<nn;i++){int x=find(edge[i].u),y=find(edge[i].v);if(x!=y){fa[x]=y;if(edge[i].state==0) sum+=edge[i].w;total++;}}if(total<n-1) cout<<"no"<<endl;cout<<sum<<endl;}return 0;
}

DreamJudge 1341 还是畅通工程 

#include<bits/stdc++.h>
using namespace std;
const int maxm=105;
struct node{int u,v,w;
}edge[maxm*maxm];
int fa[maxm];
bool cmp(node a,node b) {return a.w<b.w;}
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int main()
{int n;while(cin>>n){if(n==0) break;int nn=n*(n-1)/2;for(int i=0;i<nn;i++) cin>>edge[i].u>>edge[i].v>>edge[i].w;for(int i=1;i<=n;i++) fa[i]=i;sort(edge,edge+nn,cmp);int sum=0;for(int i=0;i<nn;i++){int x=find(edge[i].u),y=find(edge[i].v);if(x!=y){fa[x]=y;sum+=edge[i].w;}}cout<<sum<<endl;}return 0;
}

DreamJudge 1183 Freckles 🍩

#include<bits/stdc++.h>
using namespace std;
const int maxm=105;
struct node{double x,y;
}vec[maxm];
struct edg{int u,v;double len;
}edge[maxm*maxm];
int fa[maxm];
bool cmp(edg a,edg b) {return a.len<b.len;}
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int main()
{int n;while(cin>>n){for(int i=1;i<=n;i++){cin>>vec[i].x>>vec[i].y;fa[i]=i;}int nn=n*(n-1)/2;int cnt=0;for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){edge[cnt].u=i;edge[cnt].v=j;edge[cnt++].len=sqrt(pow((vec[i].x-vec[j].x),2)+pow((vec[i].y-vec[j].y),2));}}sort(edge,edge+nn,cmp);int total=0;double sum=0;for(int i=0;i<nn;i++){int x=find(edge[i].u),y=find(edge[i].v);if(x!=y){fa[x]=y;sum+=edge[i].len;total++;}if(total==n-1) break;}cout<<fixed<<setprecision(2)<<sum<<endl;}return 0;
}

DreamJudge 1234 Jungle Roads 🍩

 

#include <bits/stdc++.h>
using namespace std;
const int maxm=105;
int fa[maxm];
struct node{int u,v,w;
}edge[maxm];
bool cmp(node a,node b){return a.w<b.w;
}
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int main()
{int n;while (cin>>n){if(n==0) return 0;int nn=0;for(int i=0;i<n-1;i++){char cur;int m;cin>>cur>>m;int u=cur-'A'+1;while(m--){char tar;int w;cin>>tar>>w;int v=tar-'A'+1;edge[nn++]={u,v,w};}}for(int i=1;i<=n;i++) fa[i]=i;sort(edge,edge+nn,cmp);int sum=0,total=0;for(int i=0;i<nn;i++){int x=find(edge[i].u),y=find(edge[i].v);if(x!=y){fa[x]=y;sum+=edge[i].w;total++;}}if(total==n-1) cout<<sum<<endl;}return 0;
}

🧊🧊🧊7.5 最短路径问题

Floyd 算法特点：

1、适合求多源最短路径

2、可以求最小环

3、可以有负边权，不能有负环

4、可以求有向图的传递闭包

5、时间复杂度 O(n^3)

单源最短路径算法的选择：

  • Dijkstra + 堆优化：无法处理负边权的问题
  • SPFA + 堆优化：期望复杂度很优秀，但是复杂度不稳定

一般来说，计算机考研机试，几乎不可能出现故意构造大量数据使得 SPFA 超时的情况，就如同不可能在机试中故意构造数据使得 sort 函数的复杂度退化到 O(n^2)一样。

当然，后面也附上 Dijkstra 的通用算法模板以备不时之需。

🥥例题：DreamJudge 1565

 spfa：

/* spfa + vector
SPFA 可以有负边权、可以用一点个入队是否超过 N 次判断是否存在负环
*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int n, m;
struct Edge{int u, v, w;Edge(int u, int v, int w):u(u),v(v),w(w) {}
};
vector<Edge> edges;
vector<int> G[maxn];
int dist[maxn]; // 存放起点到 i 点的最短距离
int vis[maxn]; // 标记是否访问过
int p[maxn]; // 存放路径
void spfa(int s) {queue<int> q; // 如果这个 spfa 超时的时候可以把队列改为和 dijkstra 一样的优先队列for (int i = 0; i <= n; i++) dist[i] = INF;dist[s] = 0;memset(vis, 0, sizeof(vis));q.push(s);while (!q.empty()) {int u = q.front(); q.pop();vis[u] = 0;for (int i = 0; i < G[u].size(); i++) {Edge& e = edges[G[u][i]];if (dist[e.v] > dist[u] + e.w) { // 松弛过程dist[e.v] = dist[u] + e.w;p[e.v] = u; // 松弛过程 记录路径if (!vis[e.v]) {vis[e.v] = 1;q.push(e.v);}}}}
}
void addedge(int u, int v, int w) {edges.push_back(Edge(u, v, w));int sz = edges.size();G[u].push_back(sz - 1);
}
void init() {for(int i = 0; i <= n; i++) G[i].clear();edges.clear();
}
int main() {while (scanf("%d%d", &n, &m) != EOF) {if (n + m == 0) break;init();for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);addedge(a, b, c);addedge(b, a, c);}spfa(1);printf("%d\n",dist[n]);}return 0;
}

floyd：

/*flody 算法可以求多源最短路径
*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int mpt[maxn][maxn];
int n, m;
void floyd() {for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {mpt[i][j] = min(mpt[i][k] + mpt[k][j], mpt[i][j]);}}}
}
int main() {while (scanf("%d%d", &n, &m) != EOF) {if (n + m == 0) break;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) mpt[i][j] = 0;else mpt[i][j] = INF;}}for (int i = 1; i <= m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);if (c < mpt[a][b]) { //注意重边mpt[a][b] = c;mpt[b][a] = c;}}floyd();printf("%d\n",mpt[1][n]);}return 0;
}

dijkstra：

// dijkstra + 堆优化
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int n, m;
struct Edge{int u, v, w;Edge(int u, int v, int w):u(u),v(v),w(w) {}
};
struct node {int d, u;node(int d, int u):d(d),u(u) {}friend bool operator < (node a, node b) {return a.d > b.d;}
};
vector<Edge> edges;
vector<int> G[maxn];
int dist[maxn]; // 存放起点到 i 点的最短距离
int vis[maxn]; // 标记是否访问过
int p[maxn]; // 存放路径
void dijkstra(int s) {priority_queue<node> q;for (int i = 0; i <= n; i++) dist[i] = INF;dist[s] = 0;memset(vis, 0, sizeof(vis));q.push(node(0, s));int cnt = 0; //统计松弛次数while (!q.empty()) {node now = q.top(); q.pop();int u = now.u;if (vis[u]) continue;vis[u] = 1;cnt++;if(cnt >= n) break; // 小优化for (int i = 0; i < G[u].size(); i++) { // // Sum -> O(E)Edge& e = edges[G[u][i]];if (dist[e.v] > dist[u] + e.w) { // O(lgV)dist[e.v] = dist[u] + e.w;p[e.v] = G[u][i];q.push(node(dist[e.v], e.v));}}}
}
void addedge(int u, int v, int w) {edges.push_back(Edge(u, v, w));int sz = edges.size();G[u].push_back(sz - 1);
}
void init() {for(int i = 0; i <= n; i++) G[i].clear();edges.clear();
}
int main() {while (scanf("%d%d", &n, &m) != EOF) {if (n + m == 0) break;init();for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);addedge(a, b, c);addedge(b, a, c);}dijkstra(1);printf("%d\n",dist[n]);}return 0;
}

C语言模板：

spfa：

#include<stdio.h>
#include<string.h>
#define INF 0x7ffffff
struct node {int to, next, val;
}edge[100005];//边的数量 100005
int head[1005];//点的数量 1005
int dist[1005];
int vis[1005];
int Q[100005];//定义一个数组模拟的队列
void SPFA(int s, int n) {//SPFA 算法模板int l = 0;//定义队首int r = 0;//定义队尾memset(vis,0,sizeof(vis));for(int i = 1; i <= n; i++)dist[i] = INF;dist[s] = 0;vis[s] = 1;Q[r++] = s;//将起点入队while (l < r) {//当队列不为空int now = Q[l];//取队首元素l++; //出队vis[now] = 0;for(int i = head[now];i != -1;i = edge[i].next) {int to = edge[i].to;if(dist[to] > dist[now] + edge[i].val) {dist[to] = dist[now] + edge[i].val;if(vis[to] == 0) {vis[to] = 1;Q[r++] = to; //将点 to 入队}}}}
}
int k;
void init() {//初始化k = 0;memset(head, -1, sizeof(head));
}
void add(int x, int y, int val) {//加边操作edge[k].to = y;edge[k].val = val;edge[k].next = head[x];head[x] = k++;
}
int main() {int n, m;while(scanf("%d%d", &n, &m) != EOF){if(n == 0 && m == 0)break;init();int a, b, c;for(int i = 1; i <= m; i++) {scanf("%d%d%d", &a, &b, &c);add(a, b, c);//加入有向边 a->b 权值为 cadd(b, a, c);}SPFA(1, n);//传入起点和点的数量printf("%d\n", dist[n]);}return 0;
}

🥥练习题目：

DreamJudge 1344 最短路径问题 

#include<bits/stdc++.h>
using namespace std;
const int maxm=1010;
int main()
{int n,m;int dp[maxm][maxm],cost[maxm][maxm];//用memset，不能直接赋值，会出错while(cin>>n>>m){if(n==0&&m==0) break;memset(dp,0x3f,sizeof(dp));//注意这两行memset(cost,0x3f,sizeof(cost));for(int i=0;i<m;i++){int a,b,d,p;cin>>a>>b>>d>>p;if(d<dp[a][b]){dp[a][b]=dp[b][a]=d;cost[a][b]=cost[b][a]=p;}else if(d==dp[a][b]&&p<cost[a][b]){//这里注意cost[a][b]=cost[b][a]=p;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(dp[i][j]>dp[i][k]+dp[k][j]){dp[i][j]=dp[i][k]+dp[k][j];cost[i][j]=cost[i][k]+cost[k][j];}else if(dp[i][j]==dp[i][k]+dp[k][j])//这里注意{if(cost[i][j]>cost[i][k]+cost[k][j])cost[i][j]=cost[i][k]+cost[k][j];}}}}			int s,t;cin>>s>>t;cout<<dp[s][t]<<" "<<cost[s][t]<<endl;}return 0;
}

DreamJudge 1286 最短路径 

#include <bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
typedef long long LL;
int d[N][N],fa[N];
int p1=100000;
int n,m;int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}LL qmi(int a,int k,int p)
{LL res=1;while(k!=0){if(k&1) res=res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}void floyd()
{for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) d[i][j]=0;else d[i][j]=d[j][i]=INF;for(int i=0;i<m;i++){int x,y;cin>>x>>y;x+=1;y+=1;if(find(x)!=find(y)){fa[find(x)]=find(y);int dist=qmi(2,i,p1);d[x][y]=d[y][x]=min(d[x][y],dist);}}floyd();for(int i=2;i<=n;i++){if(d[1][i]==INF) cout<<-1<<endl;else cout<<d[1][i]%p1<<endl;}return 0;
}

DreamJudge 1224 I Wanna Go Home 🍰

解释一下规则：

1. 城市分为阵营1和阵营2 ，每组输入的最后一行，是说明对应的每个城市所属的阵营， 如1 2 2 2 ，1 表示城市1，5 属于阵营1， 城市2，3，4属于阵营2。

2. 两头的城市是不同阵营的道路，只允许走一次，即只能跨阵营一次，继续用上例说明： 1->3 走过之后，3->5不可以再走了，因为 1->3这条路已经用掉了跨阵营的唯一一次机会，那么剩下的路只能走 3->4->2了

3. 每组输入都是让输出从城市1 到城市2的花费， 即求城市1到各城市的距离，输出数组中第二个元素。

//摘自N诺用户：sai023 
#include <bits/stdc++.h>
using namespace std;
const int N = 610;
int g[N][N];
int dist[N];
bool st[N];
int group[N];
int n,m;
int dijkstra(){memset(st,0,sizeof st);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;}st[t] = true;//if (t==2) return dist[2];for(int j = 1; j <=n;j++ ){dist[j] = min(dist[j],dist[t]+g[t][j]);}}if (dist[2]==0x3f3f3f3f) return -1;else return dist[2];
}int main(){while(cin >>n &&n){cin >>m;memset(g,0x3f,sizeof g);// 读取边信息while (m--) {int a, b, t;cin >> a >> b >> t;g[a][b] = min(t, g[a][b]);g[b][a] = min(t, g[b][a]); // 双向边}// 读取阵营信息for (int i = 1; i <= n; i++) {cin >> group[i];}// 处理不同阵营的边for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (group[i]==1&& group[j]==2) {// 不同阵营的边设置为单向边g[i][j] = min(g[i][j], g[j][i]);g[j][i] = 0x3f3f3f3f;}}}cout << dijkstra() <<endl;		}return 0;	
}

🧊🧊🧊7.6 拓扑排序

在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。

先统计所有节点的入度，对于入度为 0 的节点就可以分离出来，然后把这个节点指向的节点的入度减一。一直做改操作，直到所有的节点都被分离出来。如果最后不存在入度为 0 的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

下面是算法的演示过程：

🥥例题：DreamJudge 1566

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
bool mpt[maxn][maxn];
int lev[maxn];
vector<int> v[maxn];
priority_queue<int, vector<int>, greater<int> > q;
//拓扑排序
void topo(int n) {for (int i = 1; i <= n; i++) {(!lev[i]) q.push(i); //队列里面存的是入度为 0 的点}int flag = 0; //统计出队的元素个数while(!q.empty()) {int now = q.top();q.pop();if (flag) printf(" %d", now);else printf("%d", now);flag++;for (int i = 0; i < v[now].size(); i++) {int next = v[now][i];lev[next]--;if (!lev[next]) q.push(next);}}if (flag != n) {printf("这个图有环、并没有拓扑排序\n");}
}
int main() {int n, m;while(scanf("%d%d", &n, &m) != EOF) {memset(mpt, 0, sizeof(mpt));for (int i = 1; i <= m; i++) {int a, b;scanf("%d%d", &a, &b);mpt[a][b] = 1;}for (int i = 1; i <= n; i++) {v[i].clear();for (int j = 1; j <= n; j++) {if (mpt[i][j]) {v[i].push_back(j);lev[j]++;}}}topo(n);printf("\n");}return 0;
}

创作不易，点个赞吧~点赞收藏不迷路，感兴趣的宝子们欢迎关注该专栏~

勤奋努力的宝子们，学习辛苦了！宝子们可以收藏起来慢慢学哦~🌷🌷🌷休息下，我们下部分再见👋( •̀ ω •́ )✧~

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 5 - Linux YUM仓库及NFS共享服务
  • 使用Element UI组件时，icon图标不显示
  • python语言day9 正则表达式 和 xpath 解析html
  • QT：事件机制
  • 计算机基础知识复习8.14
  • redis随笔记
  • 位运算使用
  • 汇编语言lea指令取数组偏移地址
  • C++：priority_queue类
  • JavaScript class和正则
  • 10天速通Tkinter库——Day 5：使用config进行OptionMenu美化
  • Minio web控制台实现授权管理
  • 使用 nginx 搭建代理服务器（正向代理 https 网站）指南
  • 【Java】—— 使用Java编写程序找出100以内的质数
  • 理解类方法和静态方法：Python 中的高级函数
  • 【node学习】协程
  • 【每日笔记】【Go学习笔记】2019-01-10 codis proxy处理流程
  • ➹使用webpack配置多页面应用(MPA)
  • C++11: atomic 头文件
  • conda常用的命令
  • css属性的继承、初识值、计算值、当前值、应用值
  • Java到底能干嘛？
  • Linux快速复制或删除大量小文件
  • Nacos系列：Nacos的Java SDK使用
  • nodejs：开发并发布一个nodejs包
  • vue总结
  • 对话 CTO〡听神策数据 CTO 曹犟描绘数据分析行业的无限可能
  • 前端路由实现-history
  • 如何打造100亿SDK累计覆盖量的大数据系统
  • 为物联网而生：高性能时间序列数据库HiTSDB商业化首发！
  • 新手搭建网站的主要流程
  • #{} 和 ${}区别
  • #AngularJS#$sce.trustAsResourceUrl
  • #HarmonyOS：基础语法
  • #QT 笔记一
  • #VERDI# 关于如何查看FSM状态机的方法
  • #我与Java虚拟机的故事#连载19：等我技术变强了，我会去看你的 ​
  • %check_box% in rails :coditions={:has_many , :through}
  • (06)Hive——正则表达式
  • （19）夹钳(用于送货)
  • (2022 CVPR) Unbiased Teacher v2
  • （带教程）商业版SEO关键词按天计费系统：关键词排名优化、代理服务、手机自适应及搭建教程
  • （二十六）Java 数据结构
  • (过滤器)Filter和(监听器)listener
  • (四)js前端开发中设计模式之工厂方法模式
  • （四）图像的%2线性拉伸
  • （转载）（官方）UE4--图像编程----着色器开发
  • (转载)微软数据挖掘算法:Microsoft 时序算法(5)
  • .net core MVC 通过 Filters 过滤器拦截请求及响应内容
  • .net MySql
  • .NET 分布式技术比较
  • .NET/C#⾯试题汇总系列：⾯向对象
  • .net遍历html中全部的中文,ASP.NET中遍历页面的所有button控件
  • .net访问oracle数据库性能问题
  • .NET中的Exception处理(C#)