3.基础算法之搜索与图论

1.深度优先搜索 

深度优先搜索(DFS,Depth First Search)是一种用于遍历或搜索树或图的算法。它将当前状态按照一定的规则顺序,先拓展一步得到一个新状态,再对这个新状态递归拓展下去。如果无法拓展,则退回一步到上一个状态,再按照原先设定的规则顺序重新寻找一个状态拓展。如此搜索,直至找到目标状态,或者遍历完所有状态。常用于寻找起始点到目标点的路径。

深度优先搜索的主要作用包括:

  1. 图的遍历:深度优先搜索可以用来遍历一个图的所有顶点,从而了解图的结构和特性。
  2. 路径搜索:在图中搜索从起始顶点到目标顶点的路径时,深度优先搜索是一种常用的方法。它沿着一条路径尽可能深地搜索,直到达到目标顶点或无法继续搜索为止。
  3. 生成树和生成森林:深度优先搜索可以用来生成图的深度优先生成树或生成森林。这些结构在解决图论问题时非常有用,例如求解最小生成树、最短路径等问题。
  4. 拓扑排序:对于有向无环图(DAG),深度优先搜索可以用来进行拓扑排序。拓扑排序是将图中的顶点排成一个线性序列,使得对于每一条有向边(u, v),u在v的前面。这在解决一些依赖关系问题时非常有用。
  5. 检测环:深度优先搜索还可以用来检测一个图中是否存在环。在遍历过程中,如果发现一个已经访问过的顶点,且该顶点不是当前顶点的父顶点,则说明图中存在环。
  6. 图的连通性:深度优先搜索可以用来判断图的连通性,即判断从一个顶点是否可以到达图中的任意其他顶点。

排列问题

给定一个整数n,将数字 1~ n 排成 排,将会有很多种排列方法,现在,请你按照字典序将所有的排列方法输出

#include <iostream>
using namespace std;const int N = 10;
int path[N];  // 路径
bool visit[N]; // 访问数组void DFS(int u,int n){if(u>n){  // 搜索到第n+1个数字,前n个数字已经排好for(int i=1;i<=n;i++) printf("%d ",path[i]);printf("\n");return;}for(int i=1;i<=n;i++){if(!visit[i]){ // i没有被访问path[u] = i;  // 记录路径visit[i] = true; // 访问位DFS(u+1,n);  // 深度优先搜索visit[i] = false; // 恢复现场}}
}int main(){int n;scanf("%d",&n);DFS(1,n);return 0;
}

 n-皇后问题

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

算法思想:采用深度优先遍历解空间树,依次考虑每个皇后,从第1个位置开始试探,如果当前i个皇后均满足,则继续试探i+1,如果当前第i个皇后试探完8个位置均不满足,则回溯到第i个位置继续试探。直到找到8个皇后的位置,输出。

代码实现:

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 9;
int visit[N],col[N];bool check(int x, int y){for(int i=0;i<x;i++){if(abs(col[i]-y)==abs(i-x)) return false;  // 同一斜线}return true;
}void DFS(int u,int n){if(u==n){ // 前n层遍历完,输出for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(j!=col[i]) printf(".");else printf("Q");printf("\n");}printf("\n");return;}for(int i=0;i<n;i++)if(!visit[i] && check(u,i)){col[u] = i;   // 对应列放置元素visit[i] = 1; // 置访问位DFS(u+1,n);   // 深度优先遍历visit[i] = 0; // 恢复现场}
}int main(){int n;scanf("%d",&n);fill(col,col+N,-1); // col数组初始化为-1DFS(0,n);return 0;
}

树的重心

        给定一颗树,树中包含 n 个结点 (编号 1~ n)和n-1条无向边,请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
        重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。 

算法思想:如下图所示,删除节点后,树变成了3个连通部分,分别是节点的子树和父节点。因此我们可以利用DFS统计左右子树的节点数,上层连通部分的节点数为s3=n-s1-s2-1。重心为s1,s2,s3中较大的那个,遍历所有节点,最终取节点重心的最小值。

#include <iostream>
#include <cstring>
#include <vector>using namespace std;
struct TNode
{int id;TNode* next;
};  // 邻接表节点const int N = 1e5+10;
TNode* H[N];
int ans = N;
int visit[N];
int n;void insert(int a,int b){ // 节点插入邻接表TNode* node = new TNode;node->id = b; // 头插法插入边结点if(!H[a]) {H[a]=node;node->next = NULL;}else {TNode* p = H[a];while(p->next) p=p->next;node->next=NULL;p->next=node;}
}int DFS(int u){visit[u] = 1; // 访问节点int s, sum = 1,res = 0; // s为子节点节点数,res为最终重心,sum为以当前节点为根的子树节点数TNode* p = H[u];while(p){if(!visit[p->id]){s = DFS(p->id); // 深度优先遍历res = max(res, s); // 更新重心sum += s; // 加上子树节点数}p = p->next; // 访问当前节点下一个连接的节点}res = max(res,n-sum); // 更新重心ans = min(ans, res);  // 更新整个子树的重心return sum;
}int main(){scanf("%d",&n);int a,b;for(int i=0;i<n;i++){scanf("%d%d",&a,&b);insert(a,b);insert(b,a);}DFS(1);printf("%d",ans);return 0;
}

2.广度优先遍历

广度优先遍历(Breadth-First Traversal)是一种用于遍历或搜索树或图的算法。与深度优先遍历(Depth-First Traversal)不同,广度优先遍历会先访问离根节点近的节点,再访问离根节点远的节点。这种算法逐层访问树的节点,从根节点开始,先访问所有子节点,然后访问这些子节点的子节点,以此类推。

广度优先遍历通常使用队列(Queue)数据结构来实现。算法的基本步骤如下:

  1. 创建一个空队列,并将根节点入队。
  2. 当队列不为空时,重复以下步骤:
    a. 从队列中出队一个节点,并访问该节点。
    b. 将该节点的所有未访问过的子节点入队。
  3. 当队列为空时,算法结束。

广度优先遍历常可以用于解决最短路问题。

走迷宫

        给定一个 n x m 的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角(1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角(n,m)处,至少需要移动多少次。数据保证(1,1) 处和(n,m)处的数字为 0,且一定至少存在一条通路。

算法思想:采用广度优先遍历,一层一层遍历解空间树,尝试枚举所有情况,若遇到能够继续前进的路径,则加入队列,直到找到出口距离根节点最近的路径,即为最优解。

#include <iostream>
using namespace std;struct pos
{int x;int y;int steps; // BFS的深度
};const int N = 1110;
pos queue[N*N];
int f=-1,r=-1;
int G[N][N];
int visit[N][N]; // 入队时访问,所有元素只入队一次int BFS(int n,int m){pos u,v;u.x = 0, u.y=0,u.steps=0;queue[++r] = u; // 点1,1入队visit[0][0]=1;while (f<r)  // 队列不空{v = queue[++f]; // 取队首元素if(v.x==n-1 && v.y==m-1) return v.steps; // 到达终点else{if(v.y>0 && !G[v.x][v.y-1] && !visit[v.x][v.y-1]){ // 上u.x = v.x;u.y=v.y-1;u.steps = v.steps+1;queue[++r] = u;visit[u.x][u.y] = 1;}if(v.y<m-1 && !G[v.x][v.y+1] && !visit[v.x][v.y+1]){ // 下u.x = v.x;u.y=v.y+1;u.steps = v.steps+1;queue[++r] = u;visit[u.x][u.y] = 1;}if(v.x>0 && !G[v.x-1][v.y] && !visit[v.x-1][v.y]){ // 左u.x = v.x-1;u.y=v.y;u.steps = v.steps+1;queue[++r] = u;visit[u.x][u.y] = 1;}if(v.x<n-1 && !G[v.x+1][v.y] && !visit[v.x+1][v.y]){ // 右u.x = v.x+1;u.y=v.y;u.steps = v.steps+1;queue[++r] = u;visit[u.x][u.y] = 1;}}}}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&G[i][j]);printf("%d",BFS(n,m));return 0; 
}

八数码问题

在一个3x3的网格中,1~8这8 个数字和一个 x恰好不重不漏地分布在这 3 x 3 的网格中
例如:
1 2 3
X 4 6
7 5 8
在游戏过程中,可以把x 与其上、下、左、右四个方向之一的数字交换 (如果存在)我们的目的是通过交换,使得网格变为如下排列(称为正确排列)
1 2 3
4 5 6
7 8 X 

思想:采用广度优先遍历整个解空间树,即暴力的枚举所有的情况,直到找到距离根节点最近的解,即为所求 

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;struct Pos
{string str; // 八数码的当前状态int x;int y;int steps;  // 树的深度
};int BFS(int i, int j,string s){Pos u,v;unordered_set<string> strset;  // 集合,用于存储中间结果,以避免回溯兜圈子u.x =  i; u.y = j; u.steps = 0,u.str = s;queue<Pos> Q; // 当前节点入队Q.push(u);strset.insert(s); // 当前状态加入集合string t = "12345678x"; // 目标状态string tmps;  // x,y为x的位置while (!Q.empty()){v = Q.front(),Q.pop(); // 节点出队if(v.str == t) return v.steps; // 到达目标状态else{if(v.y>0){ // 可以向上滑动u.x = v.x, u.y = v.y-1,u.steps = v.steps +1; // 向上滑动tmps = v.str;swap(tmps[v.x*3+v.y],tmps[u.x*3+u.y]);if(strset.find(tmps)==strset.end()){ // 滑动后状态不在集合,加入集合和队列u.str = tmps;strset.insert(tmps);Q.push(u);}}if(v.y<2){ // 可以向下滑动u.x = v.x, u.y = v.y+1,u.steps = v.steps +1;tmps = v.str;swap(tmps[v.x*3+v.y],tmps[u.x*3+u.y]);if(strset.find(tmps)==strset.end()){u.str = tmps;strset.insert(tmps);Q.push(u);}}if(v.x>0){ // 可以向左滑动u.x = v.x-1, u.y = v.y,u.steps = v.steps +1;tmps = v.str;swap(tmps[v.x*3+v.y],tmps[u.x*3+u.y]);if(strset.find(tmps)==strset.end()){u.str = tmps;strset.insert(tmps);Q.push(u);}}if(v.x<2){ // 可以向右滑动u.x = v.x+1, u.y = v.y,u.steps = v.steps +1;tmps = v.str;swap(tmps[v.x*3+v.y],tmps[u.x*3+u.y]);if(strset.find(tmps)==strset.end()){u.str = tmps;strset.insert(tmps);Q.push(u);}}}}return -1; // 识别
}int main(){char str[2];string s;int x,y,k=0;for(int i=0;i<9;i++){cin >> str; // cin读入空格则返回if(str[0] == 'x'){x = i/3;y=i%3;} // x的位置s+= str;}printf("%d",BFS(x,y,s));return 0;
}

图中点的层次        

        给定一个 n 个点 m条边的有向图,图中可能存在重边和自环所有边的长度都是 1,点的编号为 1~ n。请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 -1.

算法思想:从1号节点出发,采用广度优先遍历,一层一层遍历节点,直到遍历到n号节点。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>using namespace std;
struct TNode
{int id;TNode* next;
};  // 邻接表节点const int N = 1e5+10;
TNode* H[N];
int visit[N];  // 节点访问情况
queue<int> Q; // 队列void insert(int a,int b){ // 插入边节点,采用头插法TNode* node = new TNode;node->id = b;node->next = H[a];H[a] = node;
}int BFS(int u,int n){visit[u] = 1; // 置访问位Q.push(u);  // u节点入队TNode* p;int i;int steps = 0; // 遍历到的层次while(!Q.empty()){ // 队列不空int size = Q.size(); // 当前层节点数for(int j=0;j<size;j++){i = Q.front(),Q.pop(); // 节点出队if(i == n) return steps; // 找到n节点p = H[i];while (p)  // 访问当前节点邻节点{if(!visit[p->id]){ // 节点未访问,则入队visit[p->id] = 1;Q.push(p->id);}p = p->next;}}steps++; // 当前层节点遍历完,层数+1}return -1;
}int main(){int n,m;scanf("%d%d",&n,&m);int a,b;for(int i=0;i<m;i++){scanf("%d%d",&a,&b);insert(a,b);}printf("%d",BFS(1,n));return 0;
}

3.有向图拓扑排序

算法思想:采用广度优先遍历,访问一个节点删除该节点的所有边,如果该节点的邻节点入度为0,,将节点入队。

#include <iostream>
using namespace std;struct Edge
{int id;Edge* next;
}; // 边节点const int N = 1e5+10;
Edge* G[N];
int degree[N]; // 入度
int Q[N]; // 队列
int f = -1,r=-1; // 队头和队尾void insert(int a,int b){ // 插入边节点Edge* edge = new Edge;edge->id = b;edge->next = G[a];G[a] = edge;degree[b]++;
}bool topsort(int n){for(int i=1;i<=n;i++){if(!degree[i]) // 找到入度为0的点入队Q[++r] = i;}int j;Edge* p;while (f<r){j = Q[++f]; p = G[j]; // 访问当前节点的邻节点while(p){ degree[p->id]--; // 删除边if(!degree[p->id]) Q[++r] = p->id; // 入度为0则入队p = p->next;}}return r == n-1;
}int main(){int n,m;scanf("%d%d",&n,&m);int a,b;while (m--){scanf("%d%d",&a,&b);insert(a,b);}if(topsort(n))for(int i=0;i<=r;i++) printf("%d ",Q[i]);else printf("-1");return 0;}

4.最短路问题

         

图参考:最短路问题(超详细~~)-CSDN博客

Dijkstra算法   

Dijkstra算法适用于具有非负权重的图,这意味着图中的所有边必须具有正数或零的权重。如果图具有负权重,则应使用不同的算法,例如Bellman-Ford算法。

该算法的主要步骤如下:

  1. 初始化:选定起始点,将其加入到已求出最短路径的顶点集合S中,其他顶点则加入到还未求出最短路径的顶点集合U中。同时,设置起始点到其他顶点的距离初始值。
  2. 选择下一个顶点:从集合U中选出距离起始点最短的顶点k,并将其加入到集合S中,同时从集合U中移除顶点k。
  3. 更新距离:更新集合U中各个顶点到起始点的距离,并更新它们的路径。这是通过比较从起始点通过新加入的顶点k到达其他顶点的距离与当前已知的距离来实现的。
  4. 重复步骤2和3,直到遍历完所有顶点,即集合U为空为止。

需要注意的是,Dijkstra算法并不能处理具有负权边的图。如果图中存在负权边,可能会导致算法无法正确计算最短路径。在这种情况下,需要使用其他算法,如Bellman-Ford算法或Floyd-Warshall算法。

给定一个n个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值.请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 -1。 

#include <cstring>
#include <iostream>
using namespace std;const int N = 510; // 最多节点数
int G[N][N];   // 图
int dist[N];   // 每个节点到原点最短距离
bool V[N];     // 记录已求出最短路径的边int dijkstra(int n){memset(dist,0x3f,sizeof dist); // 初始化距离为无穷dist[1]=0;  // 从第1个节点开始,距离为0int t;for(int i=1;i<=n;i++){t = -1;for(int j=1;j<=n;j++)if(!V[j] && (t==-1 || dist[t]>dist[j])) // 选择剩余节点中最短距离节点t = j;V[t] = true;            // 第t个节点已经求出最短边,标识for(int j=1;j<=n;j++)   // 更新剩余节点的最短距离dist[j] = min(dist[j],dist[t]+G[t][j]);}if(dist[n]!=0x3f3f3f3f) // 第n个节点不可达return dist[n];else return -1;
}int main(){int n,m;scanf("%d%d",&n,&m);int a,b,c;memset(G,0x3f,sizeof G);while (m--){scanf("%d%d%d",&a,&b,&c);G[a][b]=min(G[a][b],c);    // 重边合并为较短的边}printf("%d",dijkstra(n));return 0;}

        朴素的Dijkstra算法的时间复杂度是O(V^2),其中V是图中节点的数量。这是因为算法需要遍历所有节点,并对每个节点的所有邻居进行更新操作。在稠密图(即边数接近节点数平方的图)中,由于每个节点都有很多邻居,因此朴素Dijkstra算法的性能可能是可接受的。

        然而,在稀疏图(即边数远少于节点数平方的图)中,朴素Dijkstra算法可能不是最优选择。在这种情况下,使用优先队列(如二叉堆)进行优化的Dijkstra算法通常更为高效,其时间复杂度可以降低到O((V+E)log V),其中E是图中边的数量。

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;const int N = 2e5+10;struct Edge
{int id;         // 节点int d;          // 距离Edge* next; 
};Edge* H[N];  // 邻接表
int dist[N];  // 最短距离
int V[N];     // 节点标识
typedef pair<int,int> PII;void insert(int x,int y, int z){ // 头插法插入边Edge* edge = new Edge;edge->d = z;edge->id = y;edge->next = H[x];H[x] = edge;
}int dijkstra(int n){memset(dist,0x3f,sizeof dist);   // 距离初始化为无穷priority_queue<PII,vector<PII>,greater<PII>> heap; // 小根堆heap.push({0,1});  // 第一个节点入堆PII item;int id,d;Edge* p;while (heap.size()){item = heap.top();  // 最短距离节点出队heap.pop();d = item.first, id = item.second;if(V[id]) continue; // 当前节点已经求出最短距离p = H[id];while (p)          // 更新与该节点有边相连的所有节点的距离{if(dist[p->id]>d+p->d){dist[p->id] = d+p->d;heap.push({dist[p->id],p->id});V[p->id] = 1;}p = p->next;}}if(dist[n]!=0x3f3f3f3f)return dist[n];else return -1;  
}int main(){int n,m;scanf("%d%d",&n,&m);int x,y,z;while(m--){scanf("%d%d%d",&x,&y,&z);insert(x,y,z);}printf("%d",dijkstra(n));return 0;
}

bellman ford算法

        Bellman-Ford算法的核心思想是通过迭代来逐渐逼近最短路径。算法会对图中的所有边进行V-1次松弛操作(V是图中顶点的数量),每次松弛操作都会尝试更新源点到各个顶点的最短路径长度。通过多次迭代,算法最终能够计算出源点到所有其他顶点的最短路径。

        然而,Bellman-Ford算法的时间复杂度相对较高,为O(VE),其中V是顶点数,E是边数。这使得它在处理大规模图时可能效率较低。但是,Bellman-Ford算法有一个独特的优势,即它能够检测并处理负权环(即权重总和为负的环)。如果图中存在负权环,则源点到某些顶点的最短路径可能不存在(路径长度可以无限减小),此时Bellman-Ford算法能够检测出这种情况并给出相应的提示。

        在实际应用中,如果需要处理带有负权重的边或者需要检测负权环的存在,Bellman-Ford算法是一个不错的选择。但是,如果图中没有负权重边且对性能有较高要求,那么Dijkstra算法或其他更高效的算法可能更为合适。

        需要注意的是,在实现Bellman-Ford算法时,可以使用邻接表或邻接矩阵来存储图的结构。邻接表通常更为节省空间,并且在稀疏图中表现更好;而邻接矩阵在稠密图中可能更为方便。具体选择哪种存储方式取决于图的特性和实际需求。

给定一个 n 个点 m条边的有向图,图中可能存在重边和自环, 边权可能为负数,请你求出从 1 号点到 n 号点的最多经过 条边的最短距离,如果无法从 1 号点走到 n 号点,输出impossible 。

#include <iostream>
#include <cstring>
using namespace std;const int N = 510;
const int M = 1e4+10;struct Edge
{int a,b,x;
}H[M];int dist[N];
int backup[N];void bellman_ford(int n,int m,int k){memset(dist,0x3f,sizeof dist);dist[1]=0;Edge p;for(int i=1;i<=k;i++){  // 最多经过k条边,即更新k次memcpy(backup,dist,sizeof dist); // 防止串联,每次按照上次邻近节点的权值,而不是本次已经更新过的for(int j=0;j<m;j++){  // 更新每条边的距离p = H[j];dist[p.b] = min(dist[p.b],backup[p.a]+p.x);}}if(dist[n]>0x3f3f3f3f/2) printf("impossible");else printf("%d",dist[n]);
}int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);int a,b,x;for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&x);H[i] = {a,b,x};}bellman_ford(n,m,k);return 0;}

 SPFA算法

        SPFA算法的核心思想是使用队列来存储待优化的节点。初始时,将源节点加入队列,并初始化源节点到所有其他节点的距离为无穷大。然后,从队列中取出一个节点,对其所有出边进行松弛操作,即尝试更新源节点到该出边终点的最短距离。如果更新成功,且该终点不在队列中,则将其加入队列。重复这个过程,直到队列为空。

        与Bellman-Ford算法相比,SPFA算法避免了不必要的重复计算。Bellman-Ford算法会对所有边进行V-1次松弛操作,而SPFA算法只会对需要进行松弛操作的边进行处理。因此,在大多数情况下,SPFA算法的效率要高于Bellman-Ford算法。

        SPFA算法的平均时间复杂度是O(M),其中M是图的边数。然而,最坏情况下,当图中存在负权环或者故意构造的数据使得算法性能下降时,SPFA的时间复杂度可能会退化到O(NM),其中N是顶点数。

给定一个 n 个点 m条边的有向图,图中可能存在重边和自环,边权可能为负数,请你求出1号点到 n 号点的最短距离,如果无法从 1 号点走到n 号点,则输出 impossible 。数据保证不存在负权回路

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 1e5+10;struct Edge
{int id;         // 节点int d;          // 距离Edge* next; 
};Edge* H[N];   // 邻接表
int dist[N];  // 最短距离数组
int V[N];     // 队列中的节点void insert(int x,int y,int z){Edge* edge = new Edge;edge->id = y;edge->d = z;edge->next = H[x];H[x] = edge;
}void spfa(int n){memset(dist,0x3f,sizeof dist);dist[1] = 0;queue<int> q;  // 1号节点入队q.push(1);V[1] = 1;      // 1号节点在队列中int i;Edge* p;while (q.size()){i = q.front(); // 节点出队q.pop();V[i] = 0;   // 节点已经不在队列中p = H[i];   // 更新与当前节点相邻节点的距离while (p){if(dist[p->id]>dist[i]+p->d){  // 距离需要更新dist[p->id]=dist[i]+p->d;  // 更新距离if(!V[p->id]){  // 节点不在队列,节点入队q.push(p->id);V[p->id] = 1;}}p = p->next;}}if(dist[n]==0x3f3f3f3f) printf("impossible");else printf("%d",dist[n]);}int main(){int n,m;scanf("%d%d",&n,&m);int x,y,z;while (m--){scanf("%d%d%d",&x,&y,&z);insert(x,y,z);}spfa(n);return 0;}

floyd算法 

        Floyd算法,也被称为Floyd-Warshall算法,是一种用于寻找给定加权图中所有顶点对之间的最短路径的算法。它利用动态规划的思想,通过逐步构建更长的路径来找到最短路径。Floyd算法的时间复杂度为O(V^3),其中V是图中的顶点数。这意味着对于较大的图,算法可能需要较长的运行时间。但是,Floyd算法的优点在于其简单性和通用性,它可以处理带有负权重边的图,并且不需要知道图的所有信息就可以开始计算。

        Floyd算法的基本思想是通过不断更新距离矩阵来计算最短路径。初始时,距离矩阵D存储的是图中所有直接连接的顶点对之间的距离。然后,算法遍历每个顶点k,并使用k作为中间点来尝试更新其他顶点对之间的距离。具体来说,对于每对顶点i和j,算法检查是否存在一条经过顶点k的路径比当前已知的最短路径更短。如果存在这样的路径,算法就更新距离矩阵D中i和j之间的距离。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 210;
const int inf = 1e9;
int G[N][N];void floyd(int n){for(int i=1;i<=n;i++)  // 每次使用i节点更新最短距离for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)G[j][k] = min(G[j][k],G[j][i]+G[i][k]);
}int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) G[i][j] = 0;  // 对角线节点初始化为0else G[i][j] = inf;   // 节点初始化为无穷int x,y,z;while (m--){scanf("%d%d%d",&x,&y,&z);G[x][y] = min(G[x][y],z);  // 重边取较小的边}floyd(n);while (k--){scanf("%d%d",&x,&y);z = G[x][y];if(z>inf/2) puts("impossible");else printf("%d\n",z);}return 0;}

5.最小生成树

(1)prim算法

        算法思想:从一个节点出发,每次选择一条到已选择点集最短的边加入集合(且不构成环),直到已选择完n-1条边      

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
const int inf = 0x3f3f3f3f;
int G[N][N];  // 邻接矩阵
int V[N];     // 访问数组
int dist[N];  // 最短距离int prim(int n){memset(dist,inf,sizeof dist);  // 最短距离初始化为无穷int res=0;  // 最小生成树距离之和int t;for(int i = 0;i<n;i++){t = -1;for(int j=1;j<=n;j++)  // 从剩余节点中选择到当前集合最短的节点if (!V[j] && (t == -1 || dist[t] > dist[j]))t = j;if(i && dist[t]==inf) return inf; // 到集合的点不可达,图不联通if(i) res += dist[t];  // i=0时为边界值V[t] = 1;for(int k=1;k<=n;k++)  // 更新距离dist[k] = min(dist[k],G[k][t]);}return res;
}int main(){memset(G,inf,sizeof G); // 图初始化int n,m;scanf("%d%d",&n,&m);int a,b,c;while (m--){scanf("%d%d%d",&a,&b,&c); // 无向图,去除重边G[a][b] = G[b][a] = min(G[a][b],c);}int t = prim(n);if(t==inf) puts("impossible");else printf("%d",t);return 0;
}

(2)kruskal算法

        算法思想:将所有边进行排序,每次选择最短的边加入集合(不构成环),直到加入n-1条边。算法可采用并查集优化。

        给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1e5+10;
const int M = 2e5+10;
int p[N]; // 并查集父节点struct Edge
{int a,b,w;bool operator< (const Edge &W) const{ // 排序时按照w进行排序return w < W.w;}
}E[M];int find(int x){if(x != p[x]) p[x] = find(p[x]); // 路径压缩return p[x];
}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=i; // 每个节点属于一个集合int a,b,w;for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&w);E[i] = {a,b,w};}sort(E,E+m); // 边按照权重排序int pa,pb;int res=0,cnt =0; // res为最小生成树距离之和,cnt为边数for(int i=0;i<m;i++){pa = find(E[i].a);pb = find(E[i].b);if(pa!=pb){  // 最短边加入集合;pa!=pb表明至少有一个节点没有加入集合,避免环p[pa] = pb;res += E[i].w;cnt++;}}if(cnt<n-1) puts("impossible");else printf("%d",res);return 0;}

6.染色法判断二分图

        一个图是二分图,当且仅当该图中不含奇数环。而奇数环可以通过染色法判定,在染色法中,每个节点可以染成黑色或者白色,但是相邻节点颜色不能相同。如果存在奇数环,则染色后一定会出现矛盾。

给定一个 n个点 m 条边的无向图,图中可能存在重边和自环,请你判断这个图是否是二分图.

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
struct ENode  // 边结点
{int id;ENode* next;
};ENode* H[N];
int color[N];void insert(int a,int b){ // 头插法插入边ENode* node = new ENode;node->id = b;node->next = H[a];H[a] = node;
}int DFS(int u,int c){color[u] = c;  // 染色ENode* p;p = H[u];while (p){if(!color[p->id]){ // 相邻节点未染色,染成不同的颜色if(!DFS(p->id,3-c)) return 0; // 深度优先遍历染色}else if(color[p->id]==c) return 0; // 出现矛盾p = p->next;}return 1;
}int main(){int n,m;scanf("%d%d",&n,&m);int a,b;while (m--){scanf("%d%d",&a,&b);insert(a,b);insert(b,a);}bool flag = true;for(int i=1;i<=n;i++) // 有可能有多个连通分量,只要有1个连通分量存在奇数环,则不是二分图if(!color[i]){  if(!DFS(i,1)){flag = false;break;} }if(flag) puts("Yes");else puts("No");return 0;
}

7.匈牙利算法

        假设要给男生和女生进行匹配对象,有连线代表有好感,能够匹配,要求能够匹配的最多对象数。

算法思想:匈牙利算法先给每一个男生匹配他的一个看上的女生,如果出现了某个男生看中的女生已经匹配的情况,则给看中女生的对象找另一个对象来得到该女生。例如绿色连线,代表对象分手。 

 

#include <iostream>
#include <cstring>
using namespace std;struct Node  // 边结点
{int id;Node* next;
};const int N = 510;
const int M = 1e5+10;
Node* H[N];  // 邻接表
int str[N],match[N]; // match记录匹配的最终情况void insert(int u,int v){Node* node = new Node;node->id = v;node->next = H[u];H[u] = node;
}bool find(int x){Node* p = H[x];while (p){if(!str[p->id]){str[p->id] = 1; // 标记当前女生if(match[p->id]==0 || find(match[p->id])){ // 如果该女生没有对象或者该女生的对象能够匹配其他女生match[p->id] = x; // 匹配上该女生return true;}}p = p->next;}return false;
}int main(){int n1,n2,m;scanf("%d%d%d",&n1,&n2,&m);int u,v;while (m--){scanf("%d%d",&u,&v);insert(u,v);}int res = 0;for(int i=1;i<=n1;i++){memset(str,0,sizeof str); // str只是用于处理冲突的情况,循环开始初始化为0if(find(i)) res++;}printf("%d",res);return 0;
}

         参考:活动 - AcWing

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

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

相关文章

STM32 通过Modbus协议更改内部Flash(模仿EEPROM)的运行参数

main.c测试 uint8_t uart1RxBuf[64]{0};uint8_t Adc1ConvEnd0; uint8_t Adc2ConvEnd0;int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*//* Reset of all peripherals, Initial…

【C语言刷题】——初识位操作符

【C语言刷题】——初识位操作符 位操作符介绍题一、 不创建临时变量&#xff08;第三个变量&#xff09;&#xff0c;实现两个数的交换&#xff08;1&#xff09;法一&#xff08;2&#xff09;法二 题二、 求一个数存储在内存中的二进制中“一”的个数&#xff08;1&#xff0…

【算法】Hash存储——开放寻址法

模拟散列表 维护一个集合&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个整数 x&#xff1b; Q x&#xff0c;询问整数 x是否在集合中出现过&#xff1b; 现在要进行 N次操作&#xff0c;对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N&am…

C++ 之LeetCode刷题记录(三十九)

&#x1f604;&#x1f60a;&#x1f606;&#x1f603;&#x1f604;&#x1f60a;&#x1f606;&#x1f603; 开始cpp刷题之旅。 目标&#xff1a;执行用时击败90%以上使用 C 的用户。 22. 括号生成 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用…

国产软件不背黑锅:4款强大又实用的电脑软件,用了舍不得卸载

虽然一些国产软件常被误解为“流氓、付费、广告多”&#xff0c;但实际上&#xff0c;仍有许多小众却非常优质、良心的软件被大家所忽视。 1、电脑图像工具箱 这款电脑图像工具箱堪称图片处理的瑞士军刀&#xff0c;它完全免费且无任何广告干扰。这款工具箱集成了超过一百种工…

植物病害识别:YOLO水稻病害识别数据集(11000多张,yolo标注)

YOLO水稻病害识别数据集&#xff0c;包含叶斑病&#xff0c;褐斑病&#xff0c;细菌性枯萎病&#xff0c;东格鲁病毒病4个常见病害类别&#xff0c;共11000多张图像&#xff0c;yolo标注完整&#xff0c;可直接训练。 适用于CV项目&#xff0c;毕设&#xff0c;科研&#xff0c…

物联网在智慧城市建设中的关键作用:连接、感知、智能响应

一、引言 随着信息技术的飞速发展&#xff0c;物联网&#xff08;IoT&#xff09;技术已经渗透到我们生活的方方面面&#xff0c;特别是在智慧城市建设中发挥着至关重要的作用。智慧城市是指通过运用先进的信息和通信技术&#xff0c;实现城市基础设施、公共服务、交通管理、环…

SpringSecurity原理简述

文章目录 0. 简介1. 快速入门1.1 准备工作1.2 引入SpringSecurity 2. 认证2.1 登陆校验流程2.2 原理初探2.2.1 SpringSecurity完整流程2.2.2 认证流程详解 2.3 解决问题2.3.1 思路分析2.3.2 准备工作2.3.3 实现2.3.3.1 数据库校验用户准备工作核心代码实现 2.3.3.2 密码加密存储…

微信小程序onLoad加载定义好的函数

这里小程序开发中容易犯的错误-1 给客户做一个程序。需要在页面加载的时候在onLoad(options){}中加载定义好的函数&#xff0c;代码如下 onLoad(options) {get_week_()},运行时老报错 后来修改为正确的代码 onLoad(options) {this.get_week_()//必须加this},再尝试运行&#x…

项目管理工具及模板(甘特图、OKR周报、任务管理、头脑风暴等)

项目管理常用模板大全&#xff1a; 1. 项目组OKR周报 2. 项目组传统周报工作法 3. 项目甘特图 4. 团队名单 5. 招聘跟进表 6. 出勤统计 7. 年度工作日历 8. 项目工作年计划 9. 版本排期 10. 项目组任务管理 11. 项目规划模板 12. 产品分析报告 13. 头脑风暴 信息化项目建设全套…

uniapp开发DAPP钱包应用(一) 环境搭建 Vue+ MetaMask + ABI.json

上几节我们讲了如何通过Java后端完成链上交易、信息查询、以及如何使用web3插件实现开发自测。 这一节&#xff0c;我们来说说前端DAPP的开发实现。 1. MeteMask &#x1fa9c;Java对接&#xff08;BSC&#xff09;币安链 | BNB与BEP20的开发实践&#xff08;三&#xff09;水…

做一下笔记 CXDB5CCAM-MK 与 CXDBCCAM-ML 的区别

1. CXDB5CCAM-MK 的简介 2. CXDBCCAM-ML 的简介 3. 这个两个器件的区别 最基本可见的区别是 &#xff1a; 传输速度的不同。 4. 资料在资源里面

Rust入门:Rust如何调用C静态库的函数

关于Rust调用C&#xff0c;因为接口比较复杂&#xff0c;貌似Rust不打算支持。而对于C函数&#xff0c;则相对支持较好。 如果要研究C/Rust相互关系的话&#xff0c;可以参考&#xff1a; https://docs.rs/cxx/latest/cxx/ Rust ❤️ C 这里只对调用C静态库做一个最简短的介…

uniapp 解决请求出现 /sockjs-node/info?t=问题

1. uniapp请求出现 /sockjs-node/info?t问题 1.1. 问题 uniapp项目老是出现 http://192.168.2.106:8080/sockjs-node/info?t1709704280949 1.1. sockjs-node介绍 sockjs-node 是一个JavaScript库&#xff0c;提供跨浏览器JavaScript的API&#xff0c;创建了一个低延迟、全…

(golang)切片何时会创建新切片或影响原切片

什么时候切片操作会影响原切片 // 1.切片后没有触发slice的扩容机制时 什么时候对切片操作会创建新切片不影响原切片 // 2.对切片头元素进行截取的时候 // 3.当使用append时&#xff0c;len > cap则会触发扩容机制 前置&#xff1a; //slice结构体 type SliceHeader struct…

C++ 作业 24/3/11

1、提示并输入一个字符串&#xff0c;统计该字符中大写、小写字母个数、数字个数、空格个数以及其他字符个数&#xff08;要求使用C风格字符串完成&#xff09; #include <iostream>using namespace std;int main() {string str;cout << "please enter str:&…

不会还有人判断字符是否为数字或字母还用Ascii吧

不会还有人判断字符是否为数字或字母还用Ascii吧 c > a && c < z) || (c > 0 && c < 9当然&#xff0c;也可也用&#xff0c;下面给大家分享几个方法快速判断。 Character.isLetter(ch) 判断ch是否为字母 Character.isDigit(ch) 判断ch是否为数字…

#onenet网络请求http(GET,POST)

参考博文&#xff1a; POST: https://blog.csdn.net/qq_43350239/article/details/104361153 POST请求&#xff08;用串口助手测试&#xff09;&#xff1a; POST /devices/1105985351/datapoints HTTP/1.1 api-key:AdbrV5kCRsKsRCfjboYOCVcF9FY Host:api.heclouds.com Con…

爬虫入门学习(三)请求headers处理

前言 有时候请求一个网页的时候&#xff0c;无论是GET请求还是POST请求都访问不了&#xff0c;并出现403错误。这是因为这些网页为了防止恶意采集信息&#xff0c;使用了反爬机制。 正文 1、都什么原因会出现403错误呢&#xff1f; 403错误是指访问被服务器拒绝的错误。这…

魔法之线:探索string类的神秘世界

&#x1f389;个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名乐于分享在学习道路上收获的大二在校生 &#x1f648;个人主页&#x1f389;&#xff1a;GOTXX &#x1f43c;个人WeChat&#xff1a;ILXOXVJE &#x1f43c;本文由GOTXX原创&#xff0c;首发CSDN&…