导购返利网站开发,一个网站可以做多少弹窗广告,iis架设jsp网站,怎么在网上发布广告1.深度优先搜索
深度优先搜索#xff08;DFS#xff0c;Depth First Search#xff09;是一种用于遍历或搜索树或图的算法。它将当前状态按照一定的规则顺序#xff0c;先拓展一步得到一个新状态#xff0c;再对这个新状态递归拓展下去。如果无法拓展#xff0c;则退回…1.深度优先搜索
深度优先搜索DFSDepth First Search是一种用于遍历或搜索树或图的算法。它将当前状态按照一定的规则顺序先拓展一步得到一个新状态再对这个新状态递归拓展下去。如果无法拓展则退回一步到上一个状态再按照原先设定的规则顺序重新寻找一个状态拓展。如此搜索直至找到目标状态或者遍历完所有状态。常用于寻找起始点到目标点的路径。
深度优先搜索的主要作用包括
图的遍历深度优先搜索可以用来遍历一个图的所有顶点从而了解图的结构和特性。路径搜索在图中搜索从起始顶点到目标顶点的路径时深度优先搜索是一种常用的方法。它沿着一条路径尽可能深地搜索直到达到目标顶点或无法继续搜索为止。生成树和生成森林深度优先搜索可以用来生成图的深度优先生成树或生成森林。这些结构在解决图论问题时非常有用例如求解最小生成树、最短路径等问题。拓扑排序对于有向无环图DAG深度优先搜索可以用来进行拓扑排序。拓扑排序是将图中的顶点排成一个线性序列使得对于每一条有向边(u, v)u在v的前面。这在解决一些依赖关系问题时非常有用。检测环深度优先搜索还可以用来检测一个图中是否存在环。在遍历过程中如果发现一个已经访问过的顶点且该顶点不是当前顶点的父顶点则说明图中存在环。图的连通性深度优先搜索可以用来判断图的连通性即判断从一个顶点是否可以到达图中的任意其他顶点。
排列问题
给定一个整数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(un){ // 搜索到第n1个数字,前n个数字已经排好for(int i1;in;i) printf(%d ,path[i]);printf(\n);return;}for(int i1;in;i){if(!visit[i]){ // i没有被访问path[u] i; // 记录路径visit[i] true; // 访问位DFS(u1,n); // 深度优先搜索visit[i] false; // 恢复现场}}
}int main(){int n;scanf(%d,n);DFS(1,n);return 0;
} n-皇后问题 n-皇后问题是指将 n 个皇后放在 的国际象棋棋盘上使得后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 算法思想采用深度优先遍历解空间树依次考虑每个皇后从第1个位置开始试探如果当前i个皇后均满足则继续试探i1如果当前第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 i0;ix;i){if(abs(col[i]-y)abs(i-x)) return false; // 同一斜线}return true;
}void DFS(int u,int n){if(un){ // 前n层遍历完,输出for(int i0;in;i){for(int j0;jn;j)if(j!col[i]) printf(.);else printf(Q);printf(\n);}printf(\n);return;}for(int i0;in;i)if(!visit[i] check(u,i)){col[u] i; // 对应列放置元素visit[i] 1; // 置访问位DFS(u1,n); // 深度优先遍历visit[i] 0; // 恢复现场}
}int main(){int n;scanf(%d,n);fill(col,colN,-1); // col数组初始化为-1DFS(0,n);return 0;
}
树的重心 给定一颗树树中包含 n 个结点 (编号 1~ n)和n-1条无向边请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。
算法思想如下图所示删除节点后树变成了3个连通部分分别是节点的子树和父节点。因此我们可以利用DFS统计左右子树的节点数上层连通部分的节点数为s3n-s1-s2-1。重心为s1,s2,s3中较大的那个遍历所有节点最终取节点重心的最小值。 #include iostream
#include cstring
#include vectorusing namespace std;
struct TNode
{int id;TNode* next;
}; // 邻接表节点const int N 1e510;
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) pp-next;node-nextNULL;p-nextnode;}
}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 i0;in;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数据结构来实现。算法的基本步骤如下
创建一个空队列并将根节点入队。当队列不为空时重复以下步骤 a. 从队列中出队一个节点并访问该节点。 b. 将该节点的所有未访问过的子节点入队。当队列为空时算法结束。
广度优先遍历常可以用于解决最短路问题。
走迷宫 给定一个 n x m 的二维整数数组用来表示一个迷宫数组中只包含 0或 1其中 0表示可以走的路1 表示不可通过的墙壁。最初有一个人位于左上角(1,1)处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问该人从左上角移动至右下角(nm)处至少需要移动多少次。数据保证(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.y0,u.steps0;queue[r] u; // 点1,1入队visit[0][0]1;while (fr) // 队列不空{v queue[f]; // 取队首元素if(v.xn-1 v.ym-1) return v.steps; // 到达终点else{if(v.y0 !G[v.x][v.y-1] !visit[v.x][v.y-1]){ // 上u.x v.x;u.yv.y-1;u.steps v.steps1;queue[r] u;visit[u.x][u.y] 1;}if(v.ym-1 !G[v.x][v.y1] !visit[v.x][v.y1]){ // 下u.x v.x;u.yv.y1;u.steps v.steps1;queue[r] u;visit[u.x][u.y] 1;}if(v.x0 !G[v.x-1][v.y] !visit[v.x-1][v.y]){ // 左u.x v.x-1;u.yv.y;u.steps v.steps1;queue[r] u;visit[u.x][u.y] 1;}if(v.xn-1 !G[v.x1][v.y] !visit[v.x1][v.y]){ // 右u.x v.x1;u.yv.y;u.steps v.steps1;queue[r] u;visit[u.x][u.y] 1;}}}}int main(){int n,m;scanf(%d%d,n,m);for(int i0;in;i)for(int j0;jm;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_setstring strset; // 集合,用于存储中间结果,以避免回溯兜圈子u.x i; u.y j; u.steps 0,u.str s;queuePos 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.y0){ // 可以向上滑动u.x v.x, u.y v.y-1,u.steps v.steps 1; // 向上滑动tmps v.str;swap(tmps[v.x*3v.y],tmps[u.x*3u.y]);if(strset.find(tmps)strset.end()){ // 滑动后状态不在集合,加入集合和队列u.str tmps;strset.insert(tmps);Q.push(u);}}if(v.y2){ // 可以向下滑动u.x v.x, u.y v.y1,u.steps v.steps 1;tmps v.str;swap(tmps[v.x*3v.y],tmps[u.x*3u.y]);if(strset.find(tmps)strset.end()){u.str tmps;strset.insert(tmps);Q.push(u);}}if(v.x0){ // 可以向左滑动u.x v.x-1, u.y v.y,u.steps v.steps 1;tmps v.str;swap(tmps[v.x*3v.y],tmps[u.x*3u.y]);if(strset.find(tmps)strset.end()){u.str tmps;strset.insert(tmps);Q.push(u);}}if(v.x2){ // 可以向右滑动u.x v.x1, u.y v.y,u.steps v.steps 1;tmps v.str;swap(tmps[v.x*3v.y],tmps[u.x*3u.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,k0;for(int i0;i9;i){cin str; // cin读入空格则返回if(str[0] x){x i/3;yi%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 queueusing namespace std;
struct TNode
{int id;TNode* next;
}; // 邻接表节点const int N 1e510;
TNode* H[N];
int visit[N]; // 节点访问情况
queueint 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 j0;jsize;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 i0;im;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 1e510;
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 i1;in;i){if(!degree[i]) // 找到入度为0的点入队Q[r] i;}int j;Edge* p;while (fr){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 i0;ir;i) printf(%d ,Q[i]);else printf(-1);return 0;}
4.最短路问题 图参考最短路问题超详细~~-CSDN博客
Dijkstra算法
Dijkstra算法适用于具有非负权重的图这意味着图中的所有边必须具有正数或零的权重。如果图具有负权重则应使用不同的算法例如Bellman-Ford算法。
该算法的主要步骤如下
初始化选定起始点将其加入到已求出最短路径的顶点集合S中其他顶点则加入到还未求出最短路径的顶点集合U中。同时设置起始点到其他顶点的距离初始值。选择下一个顶点从集合U中选出距离起始点最短的顶点k并将其加入到集合S中同时从集合U中移除顶点k。更新距离更新集合U中各个顶点到起始点的距离并更新它们的路径。这是通过比较从起始点通过新加入的顶点k到达其他顶点的距离与当前已知的距离来实现的。重复步骤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 i1;in;i){t -1;for(int j1;jn;j)if(!V[j] (t-1 || dist[t]dist[j])) // 选择剩余节点中最短距离节点t j;V[t] true; // 第t个节点已经求出最短边,标识for(int j1;jn;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((VE)log V)其中E是图中边的数量。
#include iostream
#include cstring
#include queue
#include algorithm
#include vector
using namespace std;const int N 2e510;struct Edge
{int id; // 节点int d; // 距离Edge* next;
};Edge* H[N]; // 邻接表
int dist[N]; // 最短距离
int V[N]; // 节点标识
typedef pairint,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_queuePII,vectorPII,greaterPII 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]dp-d){dist[p-id] dp-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 1e410;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 i1;ik;i){ // 最多经过k条边,即更新k次memcpy(backup,dist,sizeof dist); // 防止串联,每次按照上次邻近节点的权值,而不是本次已经更新过的for(int j0;jm;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 i0;im;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 1e510;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;queueint 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 i1;in;i) // 每次使用i节点更新最短距离for(int j1;jn;j)for(int k1;kn;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 i1;in;i)for(int j1;jn;j)if(ij) 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(zinf/2) puts(impossible);else printf(%d\n,z);}return 0;}
5.最小生成树
1prim算法 算法思想从一个节点出发每次选择一条到已选择点集最短的边加入集合且不构成环直到已选择完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 res0; // 最小生成树距离之和int t;for(int i 0;in;i){t -1;for(int j1;jn;j) // 从剩余节点中选择到当前集合最短的节点if (!V[j] (t -1 || dist[t] dist[j]))t j;if(i dist[t]inf) return inf; // 到集合的点不可达图不联通if(i) res dist[t]; // i0时为边界值V[t] 1;for(int k1;kn;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(tinf) 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 1e510;
const int M 2e510;
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 i1;in;i) p[i]i; // 每个节点属于一个集合int a,b,w;for(int i0;im;i){scanf(%d%d%d,a,b,w);E[i] {a,b,w};}sort(E,Em); // 边按照权重排序int pa,pb;int res0,cnt 0; // res为最小生成树距离之和,cnt为边数for(int i0;im;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(cntn-1) puts(impossible);else printf(%d,res);return 0;}
6.染色法判断二分图 一个图是二分图当且仅当该图中不含奇数环。而奇数环可以通过染色法判定在染色法中每个节点可以染成黑色或者白色但是相邻节点颜色不能相同。如果存在奇数环则染色后一定会出现矛盾。
给定一个 n个点 m 条边的无向图图中可能存在重边和自环请你判断这个图是否是二分图.
#include iostream
#include cstring
using namespace std;
const int N 1e510;
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 i1;in;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 1e510;
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 i1;in1;i){memset(str,0,sizeof str); // str只是用于处理冲突的情况,循环开始初始化为0if(find(i)) res;}printf(%d,res);return 0;
}参考活动 - AcWing
