第三讲 搜索与图论
AcWing 842. 排列数字
本题用的算法思想为回溯法
排列数字1,2,3的解空间树:
可行解共有6种
顺序图解:
#include<iostream>
using namespace std;const int N = 10;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]);puts("");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()
{cin >> n;dfs(0);return 0;
}
AcWing 843. n-皇后问题
因为每行每列每条对角线都只能有一个皇后,所以可以将各行的皇后映射到同一列上,枚举每列每条对角线是否有皇后。
接着分析,对角线上的皇后。
皇后坐标为(i,j)
- 正对角线映射到一个数组dg中,由于此时
i = j + c1
的c1可能为负数,所以需要加上一个偏移量保证c1为正数,用dg[i - j + n]
记录这条正对角线 - 反对角线映射到一个数组udg,此时
i = - j + c2
,c2必定为正数,用udg[ i + j ]
记录这条反对角线
在回溯的过程中只要满足!col[i] && !dg[u - i + n] && !udg[u + i]
这个条件就表示当前的坐标能够容纳新的皇后,如此去递归枚举每个位置,找出所有合法的皇后排列即可
#include<iostream>
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]);puts("");return;}for(int i = 0; i < n; i ++ ){if(!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';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()
{cin >> n; for(int i = 0; i < n; i ++ )for(int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
}
AcWing 844. 走迷宫
引用自深度优先搜索和广度优先搜索的深入讨论
(一)深度优先搜索的特点是:
(1)无论问题的内容和性质以及求解要求如何不同,它们的程序结构都是相同的,即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构,不相同的仅仅是存储结点数据结构和产生规则以及输出要求。
(2)深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。
(3)深度优先搜索方法有广义和狭义两种理解。广义的理解是,只要最新产生的结点(即深度最大的结点)先进行扩展的方法,就称为深度优先搜索方法。在这种理解情况下,深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是,仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法,实际上是在数据库中产生一个结点之间的搜索树,因此也属于图搜索算法的范畴。
(4)不保留全部结点的深度优先搜索法,由于把扩展望的结点从数据库中弹出删除,这样,一般在数据库中存储的结点数就是深度值,因此它占用的空间较少,所以,当搜索树的结点较多,用其他方法易产生内存溢出时,深度优先搜索不失为一种有效的算法。
(5)从输出结果可看出,深度优先搜索找到的第一个解并不一定是最优解。
二、广度优先搜索法的显著特点是:
(1)在产生新的子结点时,深度越小的结点越先得到扩展,即先产生它的子结点。为使算法便于实现,存放结点的数据库一般用队列的结构。
(2)无论问题性质如何不同,利用广度优先搜索法解题的基本算法是相同的,但数据库中每一结点内容,产生式规则,根据不同的问题,有不同的内容和结构,就是同一问题也可以有不同的表示方法。
(3)当结点到跟结点的费用(有的书称为耗散值)和结点的深度成正比时,特别是当每一结点到根结点的费用等于深度时,用广度优先法得到的解是最优解,但如果不成正比,则得到的解不一定是最优解。这一类问题要求出最优解,一种方法是使用后面要介绍的其他方法求解,另外一种方法是改进前面深度(或广度)优先搜索算法:找到一个目标后,不是立即退出,而是记录下目标结点的路径和费用,如果有多个目标结点,就加以比较,留下较优的结点。把所有可能的路径都搜索完后,才输出记录的最优路径。
(4)广度优先搜索算法,一般需要存储产生的所有结点,占的存储空间要比深度优先大得多,因此程序设计中,必须考虑溢出和节省内存空间得问题。
(5)比较深度优先和广度优先两种搜索法,广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索算法法要快些。
总之,一般情况下,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快,在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时,要综合考虑。决定取舍。
走迷宫过程图解:
#include<iostream>
#include<algorithm>
#include<string.h>#define x first
#define y secondusing namespace std;const int N = 110;typedef pair<int, int> PII;int n, m;
int g[N][N]; //输入图
int d[N][N]; //记录距离,标记是否已经遍历过
PII q[N * N]; //队列int bfs()
{int hh = 0, tt = 0;q[0] = {0, 0};//初始化,未遍历的点会被标记为-1memset(d, -1, sizeof d);d[0][0] = 0;//偏移量int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};while(hh <= tt){auto t = q[hh ++ ];for(int i = 0; i < 4; i ++ ){int a = t.x + dx[i], b = t.y + dy[i];if(a < 0 || a >= n || b < 0 || b >= m) //点在这个图的范围内continue;if(g[a][b] == 0 && d[a][b] == -1) //该点可行且未被遍历过{d[a][b] = d[t.x][t.y] + 1; //距离 + 1q[ ++ tt] = {a, b}; //入队}}}return d[n - 1][m - 1];
}int main()
{cin >> n >> m;for(int i = 0; i < n; i ++ )for(int j = 0; j < m; j ++ )cin >> g[i][j];cout << bfs() << endl;return 0;
}
STL版本
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;const int N = 110, M = 110;
typedef pair<int, int> PII;
queue<PII> que;
int n, m;
int g[N][N];
int d[N][N];int bfs()
{que.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(!que.empty()){auto t = que.front();que.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;que.push({x, y});}}}return d[n-1][m-1];
}int main()
{cin >> n >> m;for(int i=0; i<n; i++)for(int j=0; j<m; j++)cin >> g[i][j];cout << bfs() << endl;return 0;
}
AcWing 845. 八数码
求最少操作步数,若无法变换则返回-1
可以利用BFS求出最小交换步数
可以将矩阵转换为字符串,用字符串来表示矩阵当前的状态
转换方法
queue<string> q; //队列直接存转换后的字符串
unordered_map<string, int> d; //利用哈希表将转换后的字符串和操作次数绑定在一起
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>using namespace std;int bfs(string start)
{//目标状态string end = "12345678x";//利用哈希表将转换后的字符串和操作次数绑定在一起queue<string> q;//利用哈希表将转换后的字符串和操作次数绑定在一起unordered_map<string, int> d;q.push(start);d[start] = 0;int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};while(q.size()){auto t = q.front();q.pop();int distance = d[t];if(t == end) return distance;//查找x的下标并转换为二维坐标int k = t.find('x');int x = k / 3, y = k % 3;for(int i = 0; i < 4; i ++ ){//转移后的x坐标int a = x + dx[i], b = y + dy[i];//x坐标未越界if(a >= 0 && a < 3 && b >= 0 && b < 3){//形态变换swap(t[k], t[a * 3 + b]);//如果状态t没有被遍历过if(!d.count(t)){d[t] = distance + 1;q.push(t);}//恢复原位swap(t[a * 3 + b], t[k]);}}}return -1;
}int main()
{string start;for(int i = 0; i < 9; i ++ ){char c;cin >> c;start += c;}cout << bfs(start) << endl;return 0;
}
AcWing 846. 树的重心
dfs(4)时,节点4
有3
,6
两个子节点,两个子节点所在的连通块的节点数加起来的值为size
节点4
的父节点1
所在连通块的节点数为n - size - 1
每个节点删去后的连通块节点数量最大值为size = max(size, n - size - 1)
,
找出使得连通块的节点数量最大值最小的点,这个点就是树的重心,利用一个全局变量ans
来记录最小值,更新方式为ans = min(ans, size)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;const int N = 1e5 + 10, M = 2 * N;int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[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 size = 0, sum = 0;//遍历节点u的子节点for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(st[j]) continue;int s = dfs(j);//size 记录所有子节点所在块的最大值size = max(size, s);//sum 将子节点所在块的值加起来sum += s;}//更新size,anssize = max(size, n - sum - 1);ans = min(ans, size);//sum初始化为0//而当前这个点(根节点)也是上一层调用dfs的根节点子节点所在连通块内的一点return sum + 1;
}int main()
{scanf("%d", &n);memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++ ){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}dfs(1);printf("%d\n", ans);return 0;
}
AcWing 847. 图中点的层次
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 1e5 + 10;queue<int> que;
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()
{//层序遍历que.push(1);memset(d, -1, sizeof d);d[1] = 0;while(!que.empty()){int t = que.front();que.pop();for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];//若未被遍历过,则距离加一if(d[j] == -1){d[j] = d[t] + 1;que.push(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;
}
AcWing 848. 有向图的拓扑序列
将入度为0的节点入队,并将这个节点的子节点入度都减一,如果入度为0,就将节点入队,如此循环,直至所有节点都入队为止。
#include<iostream>
#include<cstring>
using namespace std;const int N = 1e5 + 10;int n, m;
int h[N], ne[N], e[N], idx;
int q[N], d[N];//q表队列,d表入度void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}bool topSort()
{int hh = 0, tt = -1;for(int i = 1; i <= n; i ++ )//入度为0,入队if(!d[i])q[ ++ tt] = i;//若队列不为空while(hh <= tt){//弹出队首元素int t = q[hh ++ ];for(int i = h[t]; i != -1; i = ne[i]){ //与h[t]元素相关联的元素入度均减一int j = e[i];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 < m; 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("");}else cout << -1 << endl;return 0;
}
AcWing 849. Dijkstra求最短路 I
Dijkstra算法介绍
Dijkstra的主要特点是以起始点为中心向外层层拓展(广度优先搜索思想),直到拓展到终点为止。
算法特点:
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路
Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。
算法核心:松弛操作
//迭代n次,每次可以确定一个点到起点的最短路for(int i = 0; i < n; i ++ ){//t存储当前访问的点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]);}
过程图解
距离更新过程:
总结起来就是:每次选一个点,更新邻点,循环n−1n-1n−1次就可以了
时间复杂度O(n∗n)O(n * n)O(n∗n)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 510;int n, m;
int g[N][N];
int dist[N];//用于存储每个点到起点的最短距离
bool st[N];
//用于在更新最短距离时
//判断当前的点的最短距离是否确定 是否需要更新int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;//一号点到一号点的距离为0//迭代n次,每次可以确定一个点到起点的最短路for(int i = 0; i < n; i ++ ){//t存储当前访问的点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()
{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] = min(g[a][b], c);}int t = dijkstra();printf("%d\n", t);return 0;
}
AcWing 850. Dijkstra求最短路 II
堆优化的主要思想就是使用一个优先队列(就是每次弹出的元素一定是整个队列中最小的元素)来代替最近距离的查找,用邻接表代替邻接矩阵,这样可以大幅度节约时间开销。
在这里有几个细节需要处理:
-
首先来讲,优先队列的数据类型应该是怎样的呢?
我们知道优先队列应该用于快速寻找距离最近的点。由于优先队列只是将最小的那个元素排在前面,因此我们应该定义一种数据类型,使得它包含该节点的编号以及该节点当前与起点的距离。这里使用pair
数组来储存。 -
我们应该在什么时候对队列进行操作呢?
队列操作的地方,首先就是搜索刚开始,要为起点赋初始值,此时必须将起点加入优先队列中。该队列元素的节点编号为起点的编号,该节点当前与起点的距离为0。 -
那么如果一个节点到起点的最短距离通过其他的运算流程发生了变化,那么如何处理队列中的那个已经存入的元素?
事实上,你不需要理会队列中的元素,而是再存入一个就行了。因为如果要发生变化,只能将节点与起点之间的距离变得更小,而优先队列恰好是先让最小的那个弹出。
因此,轮到某一个队列元素弹出的时候,如果有多个元素的节点编号相同,那么被弹出的一定是节点编号最小的一个。等到后面再遇到这个节点编号的时候,我们只需要将它忽略掉就行了
时间复杂度O(mlogn)O(m log n)O(mlogn)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>using namespace std;typedef pair<int, int> PII;const int N = 1e6 + 10;int n, m;
int h[N], e[N], w[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;//如果该点已经标记过,就跳过这一轮循环st[ver] = true;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;
}
AcWing 853. 有边数限制的最短路
Bellman-Ford算法的优点是可以发现负圈,缺点是时间复杂度比Dijkstra算法高。
而SPFA算法是使用队列优化的Bellman-Ford版本,其在时间复杂度和编程难度上都比其他算法有优势。
参考文献
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 510, M = 1e4 + 10;
int n, m, k;
int 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(backup, dist, sizeof dist);for(int j = 0; j < m; j ++){int a = edges[j].a, b = edges[j].b, w = edges[j].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;
}
AcWing 851. spfa求最短路
#include<iostream>
#include<cstring>
#include<algorithm>
#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.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", &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 = spfa();if(t == -1) puts("impossible");else printf("%d\n", t);return 0;
}
AcWing 852. spfa判断负环
#include<iostream>
#include<cstring>
#include<algorithm>
#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], 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;for(int i = 1; i <= n; i ++ ){st[i] = true;q.push(i);}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(spfa()) puts("Yes");else puts("No");return 0;
}
AcWing 854. Floyd求最短路
基本思想:
弗洛伊德算法定义了两个二维矩阵:
矩阵D记录顶点间的最小路径
例如D[0][3]= 10
,说明顶点0 到 3 的最短路径为10;
矩阵P记录顶点间最小路径中的中转点
例如P[0][3]= 1
说明,0 到 3的最短路径轨迹为:0 -> 1 -> 3。
它通过3重循环,k为中转点,v为起点,w为终点,循环比较D[v][w]
和D[v][k] + D[k][w]
最小值,如果D[v][k] + D[k][w]
为更小值,则把D[v][k] + D[k][w]
覆盖保存在D[v][w]
中。
算法核心
过程图解
时间复杂度O(n∗n∗n)O(n * n * n)O(n∗n∗n)
#include<iostream>
#include<algorithm>
using namespace std;const int N = 210, INF = 1e9;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][j], d[i][k] + d[k][j]);
}int main()
{cin >> n >> m >> Q;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] = INF;while(m -- ){int a, b, w;cin >> a >> b >> w;d[a][b] = min(d[a][b], w);}floyd();while(Q -- ){int a, b;cin >> a >> b;if(d[a][b] > INF / 2) puts("impossible");else cout << d[a][b];}return 0;
}
AcWing 858. Prim算法求最小生成树
- 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。
- 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图。
- 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。
- 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
- 最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。
Prim过程图解:
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 510, INF = 0x3f3f3f3f;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[j] && (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 res;
}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");else printf("%d\n", t);return 0;
}
AcWing 859. Kruskal算法求最小生成树
此算法可以称为“加边法”,初始最小生成树边数为0
利用并查集来维护每条边所属的集合
每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
- 把图中的所有边按边权从小到大排序;
- 把图中的n个顶点看成独立的n棵树组成的森林;
- 按权值从小到大选择边,所选的边连接的两个顶点应属于两个不同的集合,并将这两颗集合合并。如果所选的两个点属于同一个集合,那么将这条边加入集合后,将会形成一个环,不符合树的定义。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
Kruskal过程图解:
#include<iostream>
#include<algorithm>using namespace std;const int N = 2e5 + 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, w;scanf("%d%d%d", &a, &b, &w);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");else printf("%d\n", res);return 0;
}
AcWing 860. 染色法判定二分图
奇数环:由奇数条边形成的一个环
把一个图的顶点划分为两个不相交子集 ,使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分,则此图为一个二分图
二分图可能含有偶数环,但一定没有奇数环,一下图形都是二分图
利用dfs对图中的点进行染色,可以判断该图是否为二分图
#include<iostream>
#include<cstring>
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 ++ ;
}//返回是否可以成功将u染色为c
bool dfs(int u, int c)
{//修改当前颜色color[u] = c;//尝试染链接边的颜色for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];//如果color[j]没有染过色if(!color[j])//如果不能将j成功染色if(!dfs(j, 3 - c)) return false;else if(color[j] == c) return false;//如果染过颜色且和u相同}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]){//如果dfs返回false 说明出现矛盾if(!dfs(i, 1)){flag = false;break;}}if(flag) puts("Yes");else puts("No");return 0;
}
AcWing 861. 二分图的最大匹配
匈牙利算法几乎是二分图匹配的核心算法,除了二分图多重匹配外均可使用
先试着给1号男生找妹子,发现第一个和他相连的1号女生还名花无主,连上一条蓝线
接着给2号男生找妹子,发现第一个和他相连的2号女生名花无主
接下来是3号男生,很遗憾1号女生已经有主了,怎么办呢?
我们试着给之前1号女生匹配的男生(也就是1号男生)另外分配一个妹子。
(黄色表示这条边被临时拆掉)
与1号男生相连的第二个女生是2号女生,但是2号女生也有主了
我们再试着给2号女生的原配重新找个妹子
2号男生可以找3号妹子~~~~~~~~ 1号男生可以找2号妹子了~~~~~~~~ 3号男生可以找1号妹子
结果就是这样
#include<iostream>
#include<cstring>
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;//那x就预定这个女孩了//如果女孩j没有男朋友,//或者她原来的男朋友能够预定其它喜欢的女孩。//配对成功,更新matchif(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;
}
如若内容造成侵权/违法违规/事实不符,请联系编程学习网邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
相关文章
- SpringCloudAlibaba:Sentinel-熔断和fegin调用
SpringCloudAlibaba:Sentinel-熔断和fegin调用 一、环境准备 父模块依赖 <properties><java.version>1.8</java.version><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><project.reporting.outputEncodi…...
2024/4/24 16:07:02 - js随机生成四位数
标题js随机生成四位数 let max9999;let min1234;let numMath.floor(Math.random()*(max-min))min; console.log(num);...
2024/4/24 15:21:32 - leetcode 335路径交叉
根据题解分析写出来 适合看看,题目比较难 public boolean isSelfCrossing(int[] distance) {int n distance.length;for (int i 3; i < n; i) {// 第 1 类路径交叉的情况if (distance[i] > distance[i - 2] && distance[i - 1] < distance[i - 3…...
2024/4/24 15:21:23 - 正数负数的源码反码补码
原码:(正数) +7 符号位 数值为 0 0000111 正数的源码最高位是0,正数的反码和原码相同,正数的补码和原码相同 原码(负数) -7 符号位 数值位 1 0000111 反码1 1111000 (负数的反码与原码符号位相同,数值为取反) 补码1 1111001 (负数的补码是在反码的基础上加1,)善…...
2024/4/24 15:21:22 - oracle 19c静默安装步骤
1.下载安装包 目前在官网下载19c时,详细的版本是 19.3,下载地址https://www.oracle.com/database/technologies/oracle19c-linux-downloads.html。 2.如果swaptotal为0,开启swap空间 rootzujian4:/home/yx# grep SwapTotal /proc/meminfo SwapTotal: 0 …...
2024/4/24 15:21:28 - 1038. 把二叉搜索树转换为累加树
1038. 把二叉搜索树转换为累加树: 题目链接 :1038. 把二叉搜索树转换为累加树 题目: 给定一个二叉搜索树,请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。 提醒一下,二叉搜索树满足下列约束条…...
2024/4/24 15:21:22 - SpringBoot核心技术-Web开发-请求参数解析原理
HandlerMapping中找到能处理请求的Handler(Controller.method())为当前Handler 找一个适配器 HandlerAdapter; RequestMappingHandlerAdapter适配器执行目标方法并确定方法参数的每一个值1、HandlerAdapter 第一个:支持方法上标注…...
2024/4/24 15:21:22 - 5-森林卫士(下)
新增知识点 计时功能 停止脚本 变量进阶 变量的重命名与删除, 变量的显示与隐藏 声音 功能及实现 增加动物角色,当动物角色被点击时扣分,并播放“失败”的音效 点击不同垃圾增加不同的分数 倒计时功能,时间到,游戏结…...
2024/4/24 15:21:19 - Android中使用ps命令查看进程PID
一.查看所有进程的PID adb shell 然后ps 各列参数意义: USER //进程当前用户; PID //Process ID,进程ID; PPID //Process Parent ID,进程的父进程ID;…...
2024/4/24 15:21:25 - 【8】测试用例设计-边界值法
边界值分析法是对软件的输入或输出边界进行测试的一种方法,它通常作为等价类划分法的一种补充测试。对于软件来说,错误经常发生在输入或输出值的关键点,即从符合需求到不符合需求的关键点,因此边界值分析法是在等价类的边界上执行…...
2024/4/24 16:07:02 - StringTable优化
StirngTable进行入池字符串时,先查找StringTable中是否有该字符串,没有才会入池,StringTable是一个hash表,适当增加StringTable中桶的数量,会减少hash碰撞的几率,提升查找效率。 package com.tech.constan…...
2024/4/24 16:07:01 - Lambda
一、构建一个线程对象,执行Runnable类型的任务。 传统方式的实现,其关键代码如下: new Thread(new Runnable() {Overridepublic void run() {System.out.println("hello");}}).start();基于JDK8中的Lambda表达式实现方式ÿ…...
2024/4/24 16:06:59 - android “android not attached to window manager”
一问题描述 这个问题是我在用ServiceWindowManger做全局弹窗时遇到的。出错的代码如下: 二问题原因 先将layout与windowmanger绑定,然后在在layout的button的触摸事件中移除了layout与windowmanger的绑定,导致button失去了上下文,…...
2024/4/24 16:07:01 - 全网最牛的基于C++11新特性线程池设计与实现【linux服务器开发】
全网最牛的基于C11新特性线程池设计与实现【linux服务器开发】专注于服务器后台开发,包括C/C,Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体&am…...
2024/4/24 16:06:57 - 权限以及修饰词
private:只能被同一包中的同一类访问 默认(包访问权限):只能被同一包中的类访问 protected:不仅能被同一包中的类访问,还能被不同包中的子类访问。 public:能被该项目当中的所有类访问 fina…...
2024/4/24 16:07:04 - English Word —— Day 24(overcome——philosophy)
...
2024/4/24 16:06:55 - VSCode之常用快捷键
shift alt a 代码格式化...
2024/4/24 16:06:55 - yolov5修改non_max_suppression支持多个置信度过滤
如题 原始的non_max_suppression def non_max_suppression(prediction, conf_thres0.25, iou_thres0.45, classesNone, agnosticFalse, multi_labelFalse,labels()):"""Runs Non-Maximum Suppression (NMS) on inference resultsReturns:list of detections, …...
2024/4/24 16:07:00 - 数据库存储过程
不带参数 DELIMITER $$USE bookshop$$DROP PROCEDURE IF EXISTS test2$$CREATE DEFINERrootlocalhost PROCEDURE test2() BEGIN DECLARE num INT DEFAULT 5;DECLARE stuTotal INT;#赋值SET num10;SET numnum2;#赋值SELECT COUNT(*) INTO stuTotal FROM users;SELECT num,stuTo…...
2024/4/24 16:06:52 - github总数换dns,总是修改hosts,双击Python脚本直接秒修改
国内访问github总是出问题 带来的体验很不爽 直接上下载地址 大多数给出的解决方案 每次无法访问就要去重新手动查询修改hosts文件, 烦的一批 于是就到github上找到了个fastHost的项目,修改了一点点, 双击直接运行(前提是安装了python3),简直无脑,放到桌面上,爽的一批 运行结…...
2024/4/24 16:06:53
最新文章
- 算法-动态规划专题
文章目录 前言 : 动态规划简述1 . 斐波那契模型1.1 泰波那契数列1.2 最小花费爬楼梯1.3 解码方法 前言 : 动态规划简述 动态规划在当前我们的理解下,其实就是一种变相的递归,我们查看一些资料也可以知道,动态规划其实属于递归的一个分支,通过把递归问题开辟的栈帧通过一定的手…...
2024/4/25 23:47:20 - 梯度消失和梯度爆炸的一些处理方法
在这里是记录一下梯度消失或梯度爆炸的一些处理技巧。全当学习总结了如有错误还请留言,在此感激不尽。 权重和梯度的更新公式如下: w w − η ⋅ ∇ w w w - \eta \cdot \nabla w ww−η⋅∇w 个人通俗的理解梯度消失就是网络模型在反向求导的时候出…...
2024/3/20 10:50:27 - 蓝桥杯第十五届抱佛脚(十)贪心算法
蓝桥杯第十五届抱佛脚(十)贪心算法 贪心算法基本概念 贪心算法是一种在算法设计中常用的方法,它在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。 贪…...
2024/4/19 0:49:59 - 24 个Intellij IDEA好用插件
24 个Intellij IDEA好用插件 一. 安装插件 Codota 代码智能提示插件 只要打出首字母就能联想出一整条语句,这也太智能了,还显示了每条语句使用频率。 原因是它学习了我的项目代码,总结出了我的代码偏好。 Key Promoter X 快捷键提示插件 …...
2024/4/22 10:07:17 - 【外汇早评】美通胀数据走低,美元调整
原标题:【外汇早评】美通胀数据走低,美元调整昨日美国方面公布了新一期的核心PCE物价指数数据,同比增长1.6%,低于前值和预期值的1.7%,距离美联储的通胀目标2%继续走低,通胀压力较低,且此前美国一季度GDP初值中的消费部分下滑明显,因此市场对美联储后续更可能降息的政策…...
2024/4/25 11:51:20 - 【原油贵金属周评】原油多头拥挤,价格调整
原标题:【原油贵金属周评】原油多头拥挤,价格调整本周国际劳动节,我们喜迎四天假期,但是整个金融市场确实流动性充沛,大事频发,各个商品波动剧烈。美国方面,在本周四凌晨公布5月份的利率决议和新闻发布会,维持联邦基金利率在2.25%-2.50%不变,符合市场预期。同时美联储…...
2024/4/25 18:39:24 - 【外汇周评】靓丽非农不及疲软通胀影响
原标题:【外汇周评】靓丽非农不及疲软通胀影响在刚结束的周五,美国方面公布了新一期的非农就业数据,大幅好于前值和预期,新增就业重新回到20万以上。具体数据: 美国4月非农就业人口变动 26.3万人,预期 19万人,前值 19.6万人。 美国4月失业率 3.6%,预期 3.8%,前值 3…...
2024/4/25 18:38:39 - 【原油贵金属早评】库存继续增加,油价收跌
原标题:【原油贵金属早评】库存继续增加,油价收跌周三清晨公布美国当周API原油库存数据,上周原油库存增加281万桶至4.692亿桶,增幅超过预期的74.4万桶。且有消息人士称,沙特阿美据悉将于6月向亚洲炼油厂额外出售更多原油,印度炼油商预计将每日获得至多20万桶的额外原油供…...
2024/4/25 18:39:23 - 【外汇早评】日本央行会议纪要不改日元强势
原标题:【外汇早评】日本央行会议纪要不改日元强势近两日日元大幅走强与近期市场风险情绪上升,避险资金回流日元有关,也与前一段时间的美日贸易谈判给日本缓冲期,日本方面对汇率问题也避免继续贬值有关。虽然今日早间日本央行公布的利率会议纪要仍然是支持宽松政策,但这符…...
2024/4/25 18:39:22 - 【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响
原标题:【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响近日伊朗局势升温,导致市场担忧影响原油供给,油价试图反弹。此时OPEC表态稳定市场。据消息人士透露,沙特6月石油出口料将低于700万桶/日,沙特已经收到石油消费国提出的6月份扩大出口的“适度要求”,沙特将满…...
2024/4/25 18:39:22 - 【外汇早评】美欲与伊朗重谈协议
原标题:【外汇早评】美欲与伊朗重谈协议美国对伊朗的制裁遭到伊朗的抗议,昨日伊朗方面提出将部分退出伊核协议。而此行为又遭到欧洲方面对伊朗的谴责和警告,伊朗外长昨日回应称,欧洲国家履行它们的义务,伊核协议就能保证存续。据传闻伊朗的导弹已经对准了以色列和美国的航…...
2024/4/25 18:39:20 - 【原油贵金属早评】波动率飙升,市场情绪动荡
原标题:【原油贵金属早评】波动率飙升,市场情绪动荡因中美贸易谈判不安情绪影响,金融市场各资产品种出现明显的波动。随着美国与中方开启第十一轮谈判之际,美国按照既定计划向中国2000亿商品征收25%的关税,市场情绪有所平复,已经开始接受这一事实。虽然波动率-恐慌指数VI…...
2024/4/25 16:48:44 - 【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试
原标题:【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试美国和伊朗的局势继续升温,市场风险情绪上升,避险黄金有向上突破阻力的迹象。原油方面稍显平稳,近期美国和OPEC加大供给及市场需求回落的影响,伊朗局势并未推升油价走强。近期中美贸易谈判摩擦再度升级,美国对中…...
2024/4/25 13:39:44 - 【原油贵金属早评】市场情绪继续恶化,黄金上破
原标题:【原油贵金属早评】市场情绪继续恶化,黄金上破周初中国针对于美国加征关税的进行的反制措施引发市场情绪的大幅波动,人民币汇率出现大幅的贬值动能,金融市场受到非常明显的冲击。尤其是波动率起来之后,对于股市的表现尤其不安。隔夜美国股市出现明显的下行走势,这…...
2024/4/25 18:39:16 - 【外汇早评】美伊僵持,风险情绪继续升温
原标题:【外汇早评】美伊僵持,风险情绪继续升温昨日沙特两艘油轮再次发生爆炸事件,导致波斯湾局势进一步恶化,市场担忧美伊可能会出现摩擦生火,避险品种获得支撑,黄金和日元大幅走强。美指受中美贸易问题影响而在低位震荡。继5月12日,四艘商船在阿联酋领海附近的阿曼湾、…...
2024/4/25 18:39:16 - 【原油贵金属早评】贸易冲突导致需求低迷,油价弱势
原标题:【原油贵金属早评】贸易冲突导致需求低迷,油价弱势近日虽然伊朗局势升温,中东地区几起油船被袭击事件影响,但油价并未走高,而是出于调整结构中。由于市场预期局势失控的可能性较低,而中美贸易问题导致的全球经济衰退风险更大,需求会持续低迷,因此油价调整压力较…...
2024/4/25 0:00:17 - 氧生福地 玩美北湖(上)——为时光守候两千年
原标题:氧生福地 玩美北湖(上)——为时光守候两千年一次说走就走的旅行,只有一张高铁票的距离~ 所以,湖南郴州,我来了~ 从广州南站出发,一个半小时就到达郴州西站了。在动车上,同时改票的南风兄和我居然被分到了一个车厢,所以一路非常愉快地聊了过来。 挺好,最起…...
2024/4/25 4:19:21 - 氧生福地 玩美北湖(中)——永春梯田里的美与鲜
原标题:氧生福地 玩美北湖(中)——永春梯田里的美与鲜一觉醒来,因为大家太爱“美”照,在柳毅山庄去寻找龙女而错过了早餐时间。近十点,向导坏坏还是带着饥肠辘辘的我们去吃郴州最富有盛名的“鱼头粉”。说这是“十二分推荐”,到郴州必吃的美食之一。 哇塞!那个味美香甜…...
2024/4/25 18:39:14 - 氧生福地 玩美北湖(下)——奔跑吧骚年!
原标题:氧生福地 玩美北湖(下)——奔跑吧骚年!让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 啊……啊……啊 两…...
2024/4/25 18:39:12 - 扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!
原标题:扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!扒开伪装医用面膜,翻六倍价格宰客!当行业里的某一品项火爆了,就会有很多商家蹭热度,装逼忽悠,最近火爆朋友圈的医用面膜,被沾上了污点,到底怎么回事呢? “比普通面膜安全、效果好!痘痘、痘印、敏感肌都能用…...
2024/4/25 2:10:52 - 「发现」铁皮石斛仙草之神奇功效用于医用面膜
原标题:「发现」铁皮石斛仙草之神奇功效用于医用面膜丽彦妆铁皮石斛医用面膜|石斛多糖无菌修护补水贴19大优势: 1、铁皮石斛:自唐宋以来,一直被列为皇室贡品,铁皮石斛生于海拔1600米的悬崖峭壁之上,繁殖力差,产量极低,所以古代仅供皇室、贵族享用 2、铁皮石斛自古民间…...
2024/4/25 18:39:00 - 丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者
原标题:丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者【公司简介】 广州华彬企业隶属香港华彬集团有限公司,专注美业21年,其旗下品牌: 「圣茵美」私密荷尔蒙抗衰,产后修复 「圣仪轩」私密荷尔蒙抗衰,产后修复 「花茵莳」私密荷尔蒙抗衰,产后修复 「丽彦妆」专注医学护…...
2024/4/25 13:19:01 - 广州械字号面膜生产厂家OEM/ODM4项须知!
原标题:广州械字号面膜生产厂家OEM/ODM4项须知!广州械字号面膜生产厂家OEM/ODM流程及注意事项解读: 械字号医用面膜,其实在我国并没有严格的定义,通常我们说的医美面膜指的应该是一种「医用敷料」,也就是说,医用面膜其实算作「医疗器械」的一种,又称「医用冷敷贴」。 …...
2024/4/25 18:38:58 - 械字号医用眼膜缓解用眼过度到底有无作用?
原标题:械字号医用眼膜缓解用眼过度到底有无作用?医用眼膜/械字号眼膜/医用冷敷眼贴 凝胶层为亲水高分子材料,含70%以上的水分。体表皮肤温度传导到本产品的凝胶层,热量被凝胶内水分子吸收,通过水分的蒸发带走大量的热量,可迅速地降低体表皮肤局部温度,减轻局部皮肤的灼…...
2024/4/25 18:38:57 - 配置失败还原请勿关闭计算机,电脑开机屏幕上面显示,配置失败还原更改 请勿关闭计算机 开不了机 这个问题怎么办...
解析如下:1、长按电脑电源键直至关机,然后再按一次电源健重启电脑,按F8健进入安全模式2、安全模式下进入Windows系统桌面后,按住“winR”打开运行窗口,输入“services.msc”打开服务设置3、在服务界面,选中…...
2022/11/19 21:17:18 - 错误使用 reshape要执行 RESHAPE,请勿更改元素数目。
%读入6幅图像(每一幅图像的大小是564*564) f1 imread(WashingtonDC_Band1_564.tif); subplot(3,2,1),imshow(f1); f2 imread(WashingtonDC_Band2_564.tif); subplot(3,2,2),imshow(f2); f3 imread(WashingtonDC_Band3_564.tif); subplot(3,2,3),imsho…...
2022/11/19 21:17:16 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机...
win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”问题的解决方法在win7系统关机时如果有升级系统的或者其他需要会直接进入一个 等待界面,在等待界面中我们需要等待操作结束才能关机,虽然这比较麻烦,但是对系统进行配置和升级…...
2022/11/19 21:17:15 - 台式电脑显示配置100%请勿关闭计算机,“准备配置windows 请勿关闭计算机”的解决方法...
有不少用户在重装Win7系统或更新系统后会遇到“准备配置windows,请勿关闭计算机”的提示,要过很久才能进入系统,有的用户甚至几个小时也无法进入,下面就教大家这个问题的解决方法。第一种方法:我们首先在左下角的“开始…...
2022/11/19 21:17:14 - win7 正在配置 请勿关闭计算机,怎么办Win7开机显示正在配置Windows Update请勿关机...
置信有很多用户都跟小编一样遇到过这样的问题,电脑时发现开机屏幕显现“正在配置Windows Update,请勿关机”(如下图所示),而且还需求等大约5分钟才干进入系统。这是怎样回事呢?一切都是正常操作的,为什么开时机呈现“正…...
2022/11/19 21:17:13 - 准备配置windows 请勿关闭计算机 蓝屏,Win7开机总是出现提示“配置Windows请勿关机”...
Win7系统开机启动时总是出现“配置Windows请勿关机”的提示,没过几秒后电脑自动重启,每次开机都这样无法进入系统,此时碰到这种现象的用户就可以使用以下5种方法解决问题。方法一:开机按下F8,在出现的Windows高级启动选…...
2022/11/19 21:17:12 - 准备windows请勿关闭计算机要多久,windows10系统提示正在准备windows请勿关闭计算机怎么办...
有不少windows10系统用户反映说碰到这样一个情况,就是电脑提示正在准备windows请勿关闭计算机,碰到这样的问题该怎么解决呢,现在小编就给大家分享一下windows10系统提示正在准备windows请勿关闭计算机的具体第一种方法:1、2、依次…...
2022/11/19 21:17:11 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”的解决方法...
今天和大家分享一下win7系统重装了Win7旗舰版系统后,每次关机的时候桌面上都会显示一个“配置Windows Update的界面,提示请勿关闭计算机”,每次停留好几分钟才能正常关机,导致什么情况引起的呢?出现配置Windows Update…...
2022/11/19 21:17:10 - 电脑桌面一直是清理请关闭计算机,windows7一直卡在清理 请勿关闭计算机-win7清理请勿关机,win7配置更新35%不动...
只能是等着,别无他法。说是卡着如果你看硬盘灯应该在读写。如果从 Win 10 无法正常回滚,只能是考虑备份数据后重装系统了。解决来方案一:管理员运行cmd:net stop WuAuServcd %windir%ren SoftwareDistribution SDoldnet start WuA…...
2022/11/19 21:17:09 - 计算机配置更新不起,电脑提示“配置Windows Update请勿关闭计算机”怎么办?
原标题:电脑提示“配置Windows Update请勿关闭计算机”怎么办?win7系统中在开机与关闭的时候总是显示“配置windows update请勿关闭计算机”相信有不少朋友都曾遇到过一次两次还能忍但经常遇到就叫人感到心烦了遇到这种问题怎么办呢?一般的方…...
2022/11/19 21:17:08 - 计算机正在配置无法关机,关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机...
关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!关机提示 windows7 正在配…...
2022/11/19 21:17:05 - 钉钉提示请勿通过开发者调试模式_钉钉请勿通过开发者调试模式是真的吗好不好用...
钉钉请勿通过开发者调试模式是真的吗好不好用 更新时间:2020-04-20 22:24:19 浏览次数:729次 区域: 南阳 > 卧龙 列举网提醒您:为保障您的权益,请不要提前支付任何费用! 虚拟位置外设器!!轨迹模拟&虚拟位置外设神器 专业用于:钉钉,外勤365,红圈通,企业微信和…...
2022/11/19 21:17:05 - 配置失败还原请勿关闭计算机怎么办,win7系统出现“配置windows update失败 还原更改 请勿关闭计算机”,长时间没反应,无法进入系统的解决方案...
前几天班里有位学生电脑(windows 7系统)出问题了,具体表现是开机时一直停留在“配置windows update失败 还原更改 请勿关闭计算机”这个界面,长时间没反应,无法进入系统。这个问题原来帮其他同学也解决过,网上搜了不少资料&#x…...
2022/11/19 21:17:04 - 一个电脑无法关闭计算机你应该怎么办,电脑显示“清理请勿关闭计算机”怎么办?...
本文为你提供了3个有效解决电脑显示“清理请勿关闭计算机”问题的方法,并在最后教给你1种保护系统安全的好方法,一起来看看!电脑出现“清理请勿关闭计算机”在Windows 7(SP1)和Windows Server 2008 R2 SP1中,添加了1个新功能在“磁…...
2022/11/19 21:17:03 - 请勿关闭计算机还原更改要多久,电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机怎么办...
许多用户在长期不使用电脑的时候,开启电脑发现电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机。。.这要怎么办呢?下面小编就带着大家一起看看吧!如果能够正常进入系统,建议您暂时移…...
2022/11/19 21:17:02 - 还原更改请勿关闭计算机 要多久,配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以...
配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!配置windows update失败 还原更改 请勿关闭计算机&#x…...
2022/11/19 21:17:01 - 电脑配置中请勿关闭计算机怎么办,准备配置windows请勿关闭计算机一直显示怎么办【图解】...
不知道大家有没有遇到过这样的一个问题,就是我们的win7系统在关机的时候,总是喜欢显示“准备配置windows,请勿关机”这样的一个页面,没有什么大碍,但是如果一直等着的话就要两个小时甚至更久都关不了机,非常…...
2022/11/19 21:17:00 - 正在准备配置请勿关闭计算机,正在准备配置windows请勿关闭计算机时间长了解决教程...
当电脑出现正在准备配置windows请勿关闭计算机时,一般是您正对windows进行升级,但是这个要是长时间没有反应,我们不能再傻等下去了。可能是电脑出了别的问题了,来看看教程的说法。正在准备配置windows请勿关闭计算机时间长了方法一…...
2022/11/19 21:16:59 - 配置失败还原请勿关闭计算机,配置Windows Update失败,还原更改请勿关闭计算机...
我们使用电脑的过程中有时会遇到这种情况,当我们打开电脑之后,发现一直停留在一个界面:“配置Windows Update失败,还原更改请勿关闭计算机”,等了许久还是无法进入系统。如果我们遇到此类问题应该如何解决呢࿰…...
2022/11/19 21:16:58 - 如何在iPhone上关闭“请勿打扰”
Apple’s “Do Not Disturb While Driving” is a potentially lifesaving iPhone feature, but it doesn’t always turn on automatically at the appropriate time. For example, you might be a passenger in a moving car, but your iPhone may think you’re the one dri…...
2022/11/19 21:16:57