算法竞赛备赛之搜索与图论训练提升,暑期集训营培训

目录

1.DFS和BFS

1.1.DFS深度优先搜索

1.2.BFS广度优先搜索

2.树与图的遍历:拓扑排序

3.最短路

 3.1.迪杰斯特拉算法

3.2.贝尔曼算法

3.3.SPFA算法

3.4.多源汇最短路Floy算法

4.最小生成树

4.1.普利姆算法

4.2.克鲁斯卡尔算法

5.二分图:染色法,匈牙利算法

5.1.染色法

5.2.匈牙利算法


1.DFS和BFS

1.1.DFS深度优先搜索

深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。它从起点开始,沿着一个路径一直到达最深的节点,然后回溯到之前的节点,继续探索下一个路径,直到所有的节点都被访问过。

DFS使用一个来存储待访问的节点,它会将起点压入栈中,然后重复执行以下步骤直到栈为空:

  1. 弹出栈顶节点。

  2. 如果该节点是目标节点,则搜索结束。

  3. 否则将该节点标记为已访问,并将其所有未访问的邻居节点按照某种规则(如按字母表顺序)依次压入栈中。

使用DFS的优点是它的空间复杂度相对较小,因为它只需要存储一条路径上的节点。但是,如果搜索的图或树非常大,DFS可能会陷入死循环或者长时间运行。此外,DFS不一定能找到最优解,因为它只探索了一条路径,而不是所有可能的路径。

因此,在实际应用中,需要根据具体问题的要求选择合适的搜索算法。例如,如果需要找到最短路径,可能更适合使用广度优先搜索(Breadth-First Search, BFS)算法。

842.排列数字

给定一个整数n,将数字1~n排成一排,将会有很多排列方法。

现在,请你按照字典序将所有的排列方法输出。

#include<iostream>
using namespace std;
​
const int N = 7;
​
int n;
int path[N];
bool st[N];
​
void dfs(int u)
{if(u == n){for(int i = 0;i < n; i++)printf("%d ", path[i]);printf("\n");return;}for(int i = 1;i <= n; i++){if(!st[i]){path[u] = i;st[i] = true;dfs(u+1);st[i] = false;}}
}
​
int main()
{scanf("%d", &n);dfs(0);return 0;
}

843.n-皇后问题

n-皇后问题是指将n个皇后放在n-n的国际棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n,请你输出所有的满足条件的棋盘摆法。

法1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 20;
​
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
​
void dfs(int u)
{if(u == n){for(int i = 0;i < n; i++)puts(g[i]);printf("\n");return;}fot(int i = 1;i <= n; i++){if(!col[i] && !dg[u + i] && !udg[n - u + i]){path[u] = i;col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u+1);col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '·';}}
}
​
int main()
{scanf("%d", &n);for(int i = 0;i < n; i++){for(int j = 0;j < n; j++)g[i][j] = '·';}dfs(0);return 0;
}

法2

#include<iostream>
using namespace std;
​
const int N = 20;
​
int n;
char g[N][N];
bool row[N], col[N], dg[N * 2], udg[N * 2];
​
void dfs(int x, int y, int s)
{if(y == n){y = 0;x++;}if(x == n){if(s == n){for(int i = 0;i < n; i++)puts(g[i]);puts("");}return;}//不放皇后dfs(x, y+1, s);//放皇后if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]){g[x][y] = 'Q';row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;dfs(x, y+1, s+1);row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;g[x][y] = '.';}
}
​
int main()
{scanf("%d", &n);for(int i = 0;i < n; i++){for(int j = 0;j < n; j++){g[i][j] = '.';}}dfs(0, 0, 0);return 0;
}

1.2.BFS广度优先搜索

广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。它从起点开始,首先访问所有与起点直接相邻的节点,然后访问这些节点的相邻节点,以此类推,直到所有的节点都被访问过。

BFS使用一个队列来存储待访问的节点,它会将起点压入队列中,然后重复执行以下步骤直到队列为空:

  1. 弹出队列首部节点。

  2. 如果该节点是目标节点,则搜索结束。

  3. 否则将该节点标记为已访问,并将其所有未访问的邻居节点按照某种规则(如按字母表顺序)依次压入队列中。

使用BFS的优点是它能够保证在最少的时间内找到目标节点,因为它是按照距离从起点由近到远进行搜索的。此外,BFS也能够处理有向无环图(DAG)和图的情况。但是,如果搜索的图或树非常大,BFS可能需要较大的空间来存储队列中的节点,因此空间复杂度较大。

因此,在实际应用中,需要根据具体问题的要求选择合适的搜索算法。例如,如果需要找到深度优先搜索的最短路径,可能更适合使用深度优先搜索算法。

844.走迷宫

给定一个n*m的二维整数数组,用来表示一个迷宫,数组中只包含0成1,其中0表示可以走的路,表示不可通过的墙壁。最初,有一个人位于左上角(1, 1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问,该人从左上角移动至右下角(n, m)处,至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0,且一定至少存在1条通路。

程序代码1

#include<iostream>
#include<queue>
#include<cstring>
​
using namespace std;
​
const int N = 110;
​
typedef pair<int, int> PII;
​
int g[N][N];
int d[N][N];
int n, m;
​
int bfs()
{queue<pair<int, int>> q;q.push({0, 0});memset(d, -1, sizeof(d));d[0][0] = 0;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};while(q.size()){PII t = q.front();q.pop();for(int i = 0;i < 4; i++){int x = t.first + dx[i], y = t.second + dy[i];if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){d[x][y] = d[t.first][t.second] + 1;q.push({x, y});}}}return d[n-1][m-1];
}
​
int main()
{scanf("%d%d", &n, &m);for(int i = 0;i < n; i++)for(int j = 0;j < m; j++)scanf("%d", &g[i][j]);cout << bfs() << endl;return 0;
}

打印路径代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
​
typedef pair<int, int> PII;
const int N = 110;
​
int n, m;
int g[N][N];
int d[N][N];
int prev[N][N];
PII q[N * N];
​
int bfs()
{int hh = 0, tt = 0;q[0] = {0, 0};memset(d, -1, sizeof(d));d[0][0] = 0;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};while(hh <= tt){auto t = q[hh++];for(int i = 0;i < 4; i++){int x = t.first + dx[i], y = t.second + dy[i];if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == 0 && d[x][y] == -1){d[x][y] = d[t.first][t.second] + 1;prev[x][y] = t;q[++tt] = {x, y};}}}int x = n - 1, y = m - 1;while(x || y){cout << x << ' ' << y << endl;auto t = prev[x][y];x = t.first, y = t.second;}return d[n-1][m-1];
}
​
int main()
{scanf("%d%d", &n, &m);for(int i = 0;i < n; i++){for(int j = 0;j < m; j++){scanf("%d", g[i][j]);}}cout << bfs() << endl;return 0;
}

5 5

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

八数码

树是一种特殊的图,属于无环图。

图分为有向图和无向图。

846.树的重心

给定一棵树,树中包含n个结点(编号1~n)和n-1条无向边。

请你找出树的重心,并输出将重心删除后剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个节点,如果将这个结点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

代码

#include<iostream>
using namespace std;
​
const int N = 100010, M = N * 2;
​
int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;
​
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
​
int dfs(int u)
{st[u] = true;//标记一下int sum = 0, res = 0;for(int i = h[u];i != -1; i = ne[i]){int j = e[i];if(!st[j]){int s = dfs(j);res = max(res, s);sum += s;}}res = max(res, n - sum - 1);ans = min(ans, res);return sum + 1;
}
​
int main()
{scanf("%d", &n);memset(h, -1, sizeof(h));for(int i = 0;i < n - 1; i++){int a, b;cin >> a >> b;add(a, b), add(b, a);}dfs(1);cout << ans << endl;return 0;
}

847.图中点的层次

给定一个n个点m条边的有向图,图中可能存在重边和自环。

所有边的长度都是1,点的编号为1~n。

请你求出1号点到n点的最短距离,如果从1号点无法走到n号点,输出-1。

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 1e5 + 10;
​
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
​
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
​
int bfs()
{int hh = 0, tt = 0;q[0] = 1;memset(d, -1, sizeof(d));d[1] = 0;while(hh <= tt){int t = q[hh++];for(int i = h[t];i != -1; i = ne[i]){int j = e[i];if(d[j] == -1){d[j] = d[t] + 1;q[++tt] = j;}}}return d[n];
}
​
int main()
{cin >> n >> m;memset(h, -1, sizeof(h));for(int i = 0;i < m; i++){int a, b;cin >> a >> b;add(a, b);}cout << bfs() << endl;return 0;
}

2.树与图的遍历:拓扑排序

848.有向图的拓扑序列

给定一个n个点m条边的有向图,图中可能存在重边和自环。

请输入任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1.

若一个由图中所有点构成的序列A满足:对于图中的每一条边(x, y),x在A中都有出现在y之前,则称A是该图的一个拓扑序列。

有向无环图——拓扑图

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 1e5 + 10;
​
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
​
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
​
bool topsort()
{int hh = 0, tt = 0;for(int i = 1;i <= n; i++){if(!d[i])q[++tt] = i;}while(hh <= tt){int t = q[hh++];for(int i = h[t];i != -1; i = ne[i]){int j = e[t];d[j]--;if(d[j] == 0){q[++tt] = j;}}}return tt == n - 1;
}
​
int main()
{cin >> n >> m;memset(h, -1, sizeof(h));for(int i = 0;i < n; i++){int a, b;cin >> a >> b;add(a, b);d[b]++;}if(topsort()){for(int i = 0;i < n; i++)printf("%d ", q[i]);puts("");}elseputs("-1");cout << << endl;return 0;
}

3.最短路

最短路问题是在给定的有向图或无向图中找到从起点到终点的最短路径的问题。这个问题在计算机科学和应用数学中有着广泛的应用,例如在路由算法、交通控制和电路设计中都需要解决最短路问题。

解决最短路问题的方法主要有两种:Dijkstra算法和Bellman-Ford算法。

Dijkstra算法是一种贪心算法,它基于图论的原理,通过不断更新起点到各个节点的最短距离,最终求得起点到终点的最短路径。该算法的基本思路是从起点开始,每次选择一个距离起点最近的节点,并更新起点到各个节点的距离。通过不断重复这个过程,最终可以得到起点到终点的最短路径。

Bellman-Ford算法是一种动态规划算法,它可以处理带有负权边的图。该算法的基本思路是通过对所有节点进行多次松弛操作,逐步更新起点到各个节点的最短距离。在每次松弛操作中,该算法会检查是否存在一个节点的距离可以通过其他节点的路径得到更短的距离,如果有,则更新该节点的距离。通过多次松弛操作,该算法可以找到起点到终点的最短路径。

除了这两种算法,还有其他一些解决最短路问题的方法,例如Floyd-Warshall算法和A*算法等。不同的算法适用于不同类型的图和不同的应用场景,需要根据具体情况选择合适的算法。

uTools_1689583511271

 3.1.迪杰斯特拉算法

Dijkstra算法是一种用于解决最短路径问题的算法,它可以在带权重的图中找到从一个起点到所有其他节点的最短路径。

该算法的基本思路是从起点开始,每次选择距离最短的节点作为中转点,并将该节点的邻居节点更新距离,直到所有节点都被访问过或者没有可达的节点。

具体实现过程如下:

  1. 初始化:将起点的距离设置为0,其他节点的距离设置为无穷大。

  2. 选择中转点:从起点开始,选择距离起点最近的节点作为中转点,将该节点的距离更新为起点到该节点的距离。

  3. 更新距离:对于中转点周围的邻居节点,如果从起点到该邻居节点的距离比之前的距离更短,则更新该邻居节点的距离为起点到该邻居节点的距离。

  4. 重复步骤2和步骤3,直到所有节点都被访问过或者没有可达的节点。

  5. 输出结果:最终得到从起点到所有节点的最短路径。

Dijkstra算法的时间复杂度为O(n^2),其中n是节点的数量。如果使用堆优化可以将时间复杂度优化为O(m log n),其中m是边数。

849.Dijkstra求最短路I

给定一个n个点m条边的1有向图,图中可能存在重边和自环,所以边权均为正值。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1.

3 3

1 2 2

2 3 1

1 3 4

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 510;
​
int n, m;
int g[N][N];
int dist[N][N];
bool st[N];
​
int dijkstra()
{memset(dist, 0x3f, sizeof(dist));dist[1] = 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;st[t] = true;for(int j = 1;j <= n; j++)dist[j] = min(dist[j], dist[t] + g[t][j]);    }if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
​
int main()
{cin >> n >> m;memset(g, 0x3f, sizeof(g));while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);}int t = dijkstra();printf("%d\n", t);return 0;
}

Dijkstra求最小短路II

堆优化版dijkstra算法

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
typedef pair<int, int> PII;
​
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 dijkstra()
{memset(dist, 0x3f, sizeof(dist));dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if(st[ver]) continue;for(int i = h[ver];i != -1; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
​
int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof(h));while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}int t = dijkstra();printf("%d\n", t);return 0;
}

3.2.贝尔曼算法

Bellman-Ford算法

for循环n次,每一次循环所有边

dist[b] = min(dist[b], dist[a]) 松弛操作

dist[b] ≤ dist[a] + w三角不等式 有负权边就很难成立啦

853.有边数限制的最短路

给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。

注意:图中可能存在负权回路。

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 510, M = 10010;
​
int n, m, k;
iny dist[N], backup[N];
​
struct Edge
{int a, b, w;
}edges[M];
​
int bellman_ford()
{memset(dist, 0x3f, sizeof(dist));dist[1] = 0;for(int i = 0;i < k; i++){memcpy(bakcup, dist, sizeof(backup));for(int j = 0;j < m; j++){int a = edges[j].a, b = edges[i].b, w = edges[i].w;dist[b] = min(dist[b], backup[a] + w);}}if(dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n];
}
​
int main()
{scanf("%d%d%d", &n, &m, &k);for(int i = 0;i < m; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w};}int t = bellman_ford();if(t == -1)puts("impossible");else printf("%d\n", t);return 0;
}

3.3.SPFA算法

851.spfa求最短路

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
​
using namespace std;
​
typedef pair<int, int> PII;
​
const int N = 510, M = 10010;
​
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.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];if(!st[j]){q.push(j);st[j] = true;}}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
​
int main()
{scanf("%d%d%d", &a, &b, &c);memset(h, -1, sizeof(h));while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}int t = spfa();if(t == -1)puts("");elseprintf("%d\n", t);return 0;
}

852.spfa判断负环

给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。

请你判断图中是否存在负权回路。

3 3

1 2 -1

2 3 4

3 1 -4

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 10010;
​
int n, m;
int h[N], w[N], e[N], ne[N], 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++;
}
​
int spfa()
{queue<int> q;q.push(1);st[1] = 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])){q.push(j);st[j] = true;}}}}return false;
}
​
int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof(h));while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}if(spaf())printf("Yes\n");elseprintf("No\n");return 0;
}

3.4.多源汇最短路Floy算法

for(int k = 1;k <= n; k++)
{for(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]);}}
}

854.Floyd求最短路

给定一个n个点m条边的有向图,图中可能存在重边和闭环,边权可能为负数。

再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”

数据保证图中不存在负权回路。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 1e4 + 10;
​
int n, m, Q;
int d[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++){d[i][j] = min(d[i][k], d[k][j]);}}}
}
​
int main()
{scanf("%d%d%d", &n, &m, &Q);for(int i = 1;i <= n; i++){for(int j = 1;j <= n; j++){if(i == j)d[i][j] = 0;elsed[i][j] = INF;}}while(m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);d[a][b] = min(d[a][b], w);}floyd();while(Q--){int a, b;scanf("%d%d",&a, &b);if(d[a][b] == INF)puts("impossible");elseprintf("%d\n", d[a][b]);}return 0;
}

4.最小生成树

最小生成树的两个算法:

  1. 普利姆算法(Prim)

  2. 克鲁斯卡尔算法(Kruskal)

4.1.普利姆算法

朴素版Prim,类似于Dijkstra算法

Dijkstra算法的主体部分:

int dijkstra()
{memset(dist, -1, sizeof(dist));dist[1] = 0;for(int i = 0;i < n - 1; i++){int t = -1;for(int j = 1;j <= n; j++){if(!st[j] && (t == -1 || dist[t] > dist[j]))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];
}

prim的算法思路

dist[i] <- 正无穷

for(i = 0;i < n; i++)
{t->找到集合距离最近的点用t更新其他点到集合的距离,st[t] = true;
}

858.Prim算法求最小生成树

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负。

求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=[V],m=[E]

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和和最小的生成树被称为无向图G的最小连通图。

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
cosnt int N = 1e4 + 10;
​
int n, m;
int g[N][N];
int dist[N];
bool st[N];
​
int prim()
{memset(dist, 0x3f, sizeof(dist));int res = 0;for(int i = 0;i < n; i++){int t = -1;for(int j = 1;j <= n; j++){if(!st[t] && (t == -1 || dist[t] > dist[j]))t = j;if(i && dist[t] == INF)return INF;if(i)res += dist[t];for(int j = 1;j <= n; j++)dist[j] = min(dist[j], g[t][j]);st[t] = true;}}return true;
}
​
int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof(g));while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = min(g[a][b], c);}int t = prim();if(t == INF)puts("impossible");elseprintf("%d\n", t);return 0;
}

堆优化版Prim

竞赛中实际上用到的不多。

4.2.克鲁斯卡尔算法

Kruskal算法的基本思想:

  1. 将所有边按照权重从小到大排序

  2. 枚举每条边a,b,权重c 如果a,b不连通,就将这条边加入到这个集合里面

859.Kruskal算法求最小生成树

4 5

1 2 1

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 1e4 + 10;
​
int n, m;
int p[N];
​
struct Edge
{int a, b, w;bool operator< (const Edge &W)const{return w < W.w;}
}edges[N];
​
int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];}
​
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, w};}sort(edges, edges + m);for(int i = 1;i <= n; i++)p[i] = i;int res = 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;res += w;cnt++;}}if(cnt < n - 1)puts("impossible");elseprintf("%d\n", res);return 0;
}

5.二分图:染色法,匈牙利算法

二分图当且仅当图中不含奇数环。

二分图又叫二部图,是图论中的一种特殊模型。设G=(V,E)是无向图,如果根据顶点V可分割为两个互不相交的子集(A,B),且图中的每条边(i,j)所关联的两个顶点i和j分属这两个不同的顶点集(i∈A,j∈B),则图G就是一个二分图。简单来说,就是顶点集V可分割为两个互不相交的子集,且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

二分图有最大匹配和最小匹配问题,在二分图中的一个匹配是指边集中任意两条边都不依附于同一个顶点,极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数,最大匹配是所有极大匹配当中边数最大的一个匹配。

分辨是否是二分图:

  1. 染色法 O(n + m)

  2. 匈牙利算法 O(mn),实际运行时间一般远小于O(mn)

5.1.染色法

二分图染色法是一种判断二分图的方法,可以分为连通图判断和非连通图判断1。

染色思路如下:

  1. 初始所有顶点未染色。

  2. 随意取出一个未染色的顶点u,把它染成一种颜色(假设为0)。

  3. 取与它连接的结点v,如果v未染色,则将v染成和u不同的颜色(假设为1),如果v已经染色,那么判断u和v颜色是否相同,相同则表明染色失败,该图不是二分图,结束。

  4. 遍历所有结点,重复步骤)。

  5. 连通图只需要一次dfs染色,非连通图则多次dfs染色。

for(int i = 1;i <= n; i++)
{if(v未染色)dfs(i);
}

860.染色法判定二分图

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 1e5 + 10, M = 2e5 + 10;
​
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
​
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
​
bool dfs(int u, int father, int c)
{color[u] = c;for(int i = h[u];i != -1; i = ne[i]){int j = e[i];if(color[j] == -1){if(!dfs(j, 3 - c)) return false;}else if(color[j] == c) return false;}return true;
}
​
int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof(h));while(m--){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}bool flag = true;for(int i = 1;i <= n; i++){if(!color[i]){if(!dfs(i, 1)){flag = false;break;}}}if(flag) puts("Yes");else puts("No");return 0;
}

题目:关押罪犯

5.2.匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。

861.二分图的最大匹配

给定一个二分图,其中左半部包含n1个点(编号1~n1),右半部包含n2个点(编号1 ~n2),二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一个部分。

请你求出二分图的最大匹配数。

给定一个二分图G,在G的一个子图M中,M的边集(E)的任意两条边都不依附于同一个顶点,则称为一个匹配。

所有匹配中包含边数最多的一组匹配称为二分图的最大匹配数。

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 510, M = 1e5 + 10;
​
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
​
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
​
bool find(int x)
{for(int i = h[x];i != -1; i = ne[i]){int j = e[i];if(!st[j]){st[j] = true;if(match[j] == 0 || find(match[j])){match[j] = x;return true;}}}return false;
}
​
int main()
{scanf("%d%d%d", &n1, &n2, &m);memset(h , -1, sizeof(h));while(m--){int a, b;scanf("%d%d", &a, &b);add(a, b);}int res = 0;for(int i = 1; i <= n1; i++){memset(st, false, sizeof(st));if(find(i)) res++;}printf("%d\n", res);return 0;
}

2 2 4

1 1

1 2

2 1

2 2

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/88911.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

浅析kubernetes部署:javashop部署概览

javashop部署概览 节点规划 首先我们对节点进行规划&#xff0c;方便起见&#xff0c;我们进行如下简单的规划&#xff1a; 这里请根据您的实际情况进行合理的资源安排&#xff0c;或和我们售后工程师讨论形成方案。 域名规划 我们以test.com为主域名规划我们的系统域名如下&…

Jpa与Druid线程池及Spring Boot整合(一): spring-boot-starter-data-jpa 搭建持久层

Jpa与Druid线程池及Spring Boot整合(一) Jpa与Druid线程池及Spring Boot整合(二)&#xff1a;几个坑 附录官网文档&#xff1a;core.domain-events域事件 (一)Jpa与Druid连接池及Spring Boot整合作为持久层,遇到系列问题,下面一 一记录&#xff1a; pom.xml 文件中加入必须的…

Linux之【进程间通信(IPC)】-总结篇

Linux之【进程间通信&#xff08;IPC&#xff09;】-总结篇 管道System V共享内存System V消息队列System V信号量IPC资源的管理方式 往期文章 1.进程间通信之管道 2.进程间通信之System V共享内存 管道 进程之间具有独立性&#xff0c;拥有自己的虚拟地址空间&#xff0c;因…

张驰咨询:提高企业竞争力,六西格玛设计公司(DFSS)在行动

六西格玛设计公司(DFSS)是一种专业从事六西格玛设计的企业&#xff0c;其主要作用是为客户提供高效的六西格玛设计服务&#xff0c;以帮助客户实现高品质、低成本和高效率的产品开发过程。六西格玛设计公司通常拥有一支专业的团队&#xff0c;具有丰富的六西格玛设计经验和技术…

Jupyter并发测试以后出现EOFError marshal data too short

Jupyter 并发测试以后出现EOFError: marshal data too short 背景 由于项目需求需要用户能进行网页在线运行python代码程序&#xff0c;调研后决定使用Jupyter的服务接口实现此功能&#xff0c;目前使用docker进行容器化部署&#xff0c;测试针对次服务进行并发测试。测试并发…

FL Studio for Windows-21.1.0.3713中文直装版功能介绍及系统配置要求

FL Studio 21简称FL水果软件,全称是&#xff1a;Fruity Loops Studio编曲&#xff0c;由于其Logo长的比较像一款水果因此&#xff0c;在大家更多的是喜欢称他为水果萝卜&#xff0c;FL studio21是目前最新的版本&#xff0c;这是一款可以让你的计算机就像是一个全功能的录音室&…

RabbitMQ:可靠消息传递的强大消息中间件

消息中间件在现代分布式系统中起着关键作用&#xff0c;它们提供了一种可靠且高效的方法来进行异步通信和解耦。在这篇博客中&#xff0c;我们将重点介绍 RabbitMQ&#xff0c;一个广泛使用的开源消息中间件。我们将深入探讨 RabbitMQ 的特性、工作原理以及如何在应用程序中使用…

Codeforces Round 891 (Div. 3)ABC

Codeforces Round 891 (Div. 3) 目录 A. Array Coloring题目大意思路代码 B. Maximum Rounding题目大意思路代码 C. Assembly via Minimums题目大意思路代码 A. Array Coloring 题目大意 给你一个包含 n n n个数字的数组&#xff0c;你的任务是判断这个数组是否可以划分成两个…

换架 3D 飞机,继续飞呀飞

相信大多数图扑 HT 用户都曾见过这个飞机的 Demo&#xff0c;在图扑发展的这十年&#xff0c;这个 Demo 是许多学习 HT 用户一定会参考的经典 Demo 之一。 这个 Demo 用简洁的代码生动地展示了 OBJ 模型加载、数据绑定、动画和漫游等功能的实现。许多用户参考这个简单的 Demo 后…

MySQL中用什么数据类型存IP地址

提到IP地址(IPv4)&#xff0c;我们脑子里肯定立马浮现类似于192.168.0.1、127.0.0.1这种常见的IP地址&#xff0c;然后结合这个问题“MySQL中用什么数据类型存IP地址&#xff1f;”&#xff0c;于是乎脱口而出用char字符串类型存储。 然后再仔细想想发现&#xff0c;这个IP地址…

腾讯云标准型CVM云服务器详细介绍

腾讯云CVM服务器标准型实例的各项性能参数平衡&#xff0c;标准型云服务器适用于大多数常规业务&#xff0c;例如&#xff1a;web网站及中间件等&#xff0c;常见的标准型云服务器有CVM标准型S5、S6、SA3、SR1、S5se等规格&#xff0c;腾讯云服务器网来详细说下云服务器CVM标准…

页面切换后,滚动栏问题

项目场景&#xff1a; 提示&#xff1a;react项目antd后台管理系统 问题描述 后台管理系统从a页面进入b页面&#xff0c;a页面有数据&#xff08;有滚动条&#xff0c;且scollTop大于0&#xff09;&#xff0c;进入b页面后&#xff0c;滚动条不是位于初始位置&#xff08;scol…

Opencv4基于C++基础入门笔记:图像 颜色 事件响应 图形 视频 直方图

效果图◕‿◕✌✌✌&#xff1a;opencv人脸识别效果图(请叫我真爱粉) 先看一下效果图勾起你的兴趣&#xff01; 文章目录&#xff1a; 一&#xff1a;环境配置搭建 二&#xff1a;图像 1.图像读取与显示 main.cpp 运行结果 2.图像色彩空间转换 2.1 换色彩 test.h …

自动化安装系统—PXE(一)

系统安装过程 加载boot loader加载启动安装菜单加载内核和initrd文件加载根系统运行anaconda的安装向导 安装光盘中与安装相关的文件 安装autofs启动后会自动出现/misc目录。 在虚拟机设置中添加CD/DVD&#xff0c;使用系统ISO文件&#xff0c;登录系统后mount /dev/cdrom …

Kettle系列(二)smart-kettle本地离线部署

Kettle系列&#xff08;二&#xff09;smart-kettle本地离线部署 说明一、概述二、代码下载&#xff08;1&#xff09;后端代码依赖下载&#xff08;2&#xff09;前端代码依赖下载 三、创建数据库&#xff08;mysql8&#xff09;四、修改配置文件五、mysql8数据库配置六、其他…

网络:路由

1. 路由器 路由器工作在三层&#xff0c;每个接口都处于不用的网段中&#xff0c;即不同的广播域。但大多情况下&#xff0c;两台路由器直接相连的接口是同一个广播域&#xff0c;即一个网段。 路由器具有判断网络地址和选择路径的功能&#xff0c;能在多网络互联的环境中&…

Mybatis一级缓存与二级缓存

Mybatis一级缓存与二级缓存 缓存就是内存中的数据&#xff0c;常常来自对数据库查询结果的保存&#xff0c;使用缓存可以避免频繁与数据库进行交互&#xff0c;从而提高查询响应速度。 mybaits提供内存支持&#xff1b; 一级缓存 一级缓存&#xff0c;sqlSession级别的缓存…

NZ系列工具NZ02:VBA读取PDF使用说明

【分享成果&#xff0c;随喜正能量】时光绽放并蒂莲&#xff0c;更是一份殷殷嘱托&#xff0c;更是一份诚挚祝福&#xff0c;是一份时光馈赠&#xff0c;又是一份时光陪伴。。 我的教程一共九套及VBA汉英手册一部&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解…

多线程事务怎么回滚?

项目中用到了多线程去批量处理一些数据&#xff0c;当时想当然认为只要方法上加上Transactional注解就好了&#xff0c;实际并未达到想要的处理效果。特此去学习了下关于多线程事务回滚相关方案&#xff0c;参考了网上其他资料&#xff0c;这里整理并记录下学习历程。 站在巨人…

VR全景智慧文旅,用科技助力旅游业振兴

引言&#xff1a; 近年来&#xff0c;科技的迅猛发展将我们带入一个全新的数字化时代&#xff0c;而虚拟现实&#xff08;Virtual Reality&#xff0c;简称VR&#xff09;技术则以其令人惊叹的全新方式&#xff0c;影响着各个领域。其中&#xff0c;旅游业作为人们探索世界、体…