AcWing基础算法课Level-2 第三讲 搜索与图论
DFS
AcWing 842. 排列数字3379人打卡
AcWing 843. n-皇后问题3071人打卡
BFS
AcWing 844. 走迷宫2965人打卡
AcWing 845. 八数码2014人打卡
树与图的深度优先遍历
AcWing 846. 树的重心2457人打卡
树与图的广度优先遍历
AcWing 847. 图中点的层次2412人打卡
拓扑排序
AcWing 848. 有向图的拓扑序列2394人打卡
Dijkstra
AcWing 849. Dijkstra求最短路 I2628人打卡
AcWing 850. Dijkstra求最短路 II2300人打卡
bellman-ford
AcWing 853. 有边数限制的最短路2169人打卡
spfa
AcWing 851. spfa求最短路2134人打卡
AcWing 852. spfa判断负环1990人打卡
Floyd
AcWing 854. Floyd求最短路2096人打卡
Prim
AcWing 858. Prim算法求最小生成树2050人打卡
Kruskal
AcWing 859. Kruskal算法求最小生成树2016人打卡
染色法判定二分图
AcWing 860. 染色法判定二分图1854人打卡
匈牙利算法
AcWing 861. 二分图的最大匹配1752人打卡
搜索与图论
AcWing 842. 排列数字
#include using namespace std; int n, c[20]; void dfs(int cur){ if(cur == n){ for(int i = 0; i < n; i++)cout<>n; dfs(0); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
AcWing 843. n-皇后问题
//c[i]:第i行的皇后放在第几列 #include using namespace std; int n, c[20], ans; void dfs(int cur){ if(cur > n){ ans++; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(c[i]==j)cout<<"Q"; else cout<<"."; } cout<<"\n"; } cout<<"\n"; } else for(int i = 1; i <= n; i++){ int ok = 1; for(int j = 1; j < cur; j++) if(c[j]==i || c[j]-j==i-cur || c[j]+j==i+cur) { ok = 0; break; } if(ok){ c[cur] = i; dfs(cur+1); } } } int main(){ cin>>n; dfs(1); //cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
AcWing 844. 走迷宫
#include using namespace std; const int maxn = 220; int n, m, a[maxn][maxn], vis[maxn][maxn]; struct node{int x,y,step;}; inline int bfs(){ int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; queueq; q.push({1,1,0}); vis[1][1]=1; while(q.size()){ node t = q.front(); q.pop(); if(t.x==n&&t.y==m)return t.step; for(int i = 0; i < 4; i++){ int nx = t.x+dx[i], ny = t.y+dy[i]; if(nx>=1&&nx<=n && ny>=1&&ny<=m &&!a[nx][ny] &&!vis[nx][ny]){ q.push({nx,ny,t.step+1}); vis[nx][ny] = 1; } } } return -1; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin>>a[i][j]; cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
AcWing 845. 八数码
//令一个棋盘表示一个状态，用字符串维护。转移的时候交换上下左右。 #include typedef long long LL; using namespace std; int dx[] = {0,0,-1,1}; int dy[] = {1,-1,0,0}; string goal = "12345678x"; unordered_mapma;//TLE int main(){ ios::sync_with_stdio(false); string s; //cin>>s; for(int i=1; i<=9;i++){string x; cin>>x; s=s+x;} if(s==goal){cout<<"0\n";return 0;} queueq; q.push(s); while(q.size()){ string t = q.front(); q.pop(); if(t==goal)break; int z; for(z=0; z < 9; z++) if(t[z]=='x')break; int x=z/3, y=z%3; for(int i = 0; i < 4; i++){ int nx=x+dx[i], ny=y+dy[i], nz=nx*3+ny; if(nx<0||nx>=3||ny<0||ny>=3)continue; string tt = t; swap(tt[z],tt[nz]); if(!ma.count(tt)){ q.push(tt); ma[tt] = ma[t]+1; } } } if(ma.count(goal))cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
AcWing 846. 树的重心
//题目：求将树的重心删除后，剩余各个连通块中点数的最大值 //思路：对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。在DFS中计算每个子树的大小，记录“向下”的子树的最大大小，利用总点数-当前子树（这里的子树指有根树的子树）的大小得到“向上”的子树的大小，然后按照定义求重心。 #include typedef long long LL; using namespace std; const int maxn = 1e5+10; int n, ans=1e9+10; vectorG[maxn]; //返回以u为根的子树中节点的个数，包括u节点 int vis[maxn]; int dfs(int u){ vis[u] = 1; int sum = 1;//加上u自己 int res = 0; for(int v : G[u]){ if(vis[v])continue; int num = dfs(v); res = max(res, num);//更新最大联通子图的节点数 sum += num; } res = max(res, n-sum);//更新从上面访问下来的vis过的 ans = min(ans, res);//更新树的重心 return sum; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i = 0; i < n-1; i++){ int u, v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1);//任意点都行 cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
AcWing 847. 图中点的层次
#include typedef long long LL; using namespace std; const int maxn = 1e5+10; vectorG[maxn]; int vis[maxn]; int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i = 1; i <= m; i++){ int u, v; cin>>u>>v; G[u].push_back(v); } queue >q; q.push({1,0}); vis[1] = 1; int ans = -1; while(q.size()){ int u = q.front().first, w = q.front().second; q.pop(); if(u==n){ans=w; break;} for(int v:G[u]){ if(!vis[v]){ vis[v] = 1; q.push({v,w+1}); } } } cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
AcWing 848. 有向图的拓扑序列
#include typedef long long LL; using namespace std; const int maxn = 1e5+10; vectorG[maxn]; int in[maxn]; int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i = 1; i <= m; i++){ int u, v; cin>>u>>v; G[u].push_back(v); in[v]++; } vectorvc; queueq; for(int i = 1; i <= n; i++) if(in[i]==0)q.push(i); while(q.size()){ int u = q.front(); q.pop(); vc.push_back(u); for(int v:G[u]){ in[v]--; if(in[v]==0)q.push(v); } } if(vc.size()1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
AcWing 849. Dijkstra求最短路 I
#include using namespace std; const int maxn = 550, inf=1e9+10; int e[maxn][maxn]; int dist[maxn], vis[maxn]; int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; memset(e,0x3f,sizeof(e)); for(int i = 1; i <= m; i++){ int u, v, w; cin>>u>>v>>w; e[u][v] = min(e[u][v], w); } int s = 1, t = n; memset(dist,0x3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[s] = 0; for(int i = 1; i <= n; i++){ int u = -1, minn = inf; for(int j = 1; j <= n; j++){ if(!vis[j] && dist[j]dist[u]+e[u][j]){ dist[j] = dist[u]+e[u][j]; } } } if(dist[t]!=e[505][505])cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
AcWing 850. Dijkstra求最短路 II
#include using namespace std; const int maxn = 2e5+10, inf=1e9+10; vector >G[maxn]; int dist[maxn], vis[maxn]; int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i = 1; i <= m; i++){ int u, v, w; cin>>u>>v>>w; G[u].push_back({v,w}); } int s = 1, t = n; memset(dist,0x3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[s] = 0; priority_queue, vector >, greater > >q; q.push({0,s}); while(q.size()){ int u = q.top().second; q.pop(); if(vis[u])continue; vis[u] = 1; for(int i = 0; i < G[u].size(); i++){ int v=G[u][i].first, w=G[u][i].second; if(dist[v]>dist[u]+w){ dist[v]=dist[u]+w; q.push(make_pair(dist[v],v)); } } } if(dist[t]!=dist[0])cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
AcWing 853. 有边数限制的最短路
/* Bellman-Ford: + 维护dist[i]表示当前到i的最短路 + 执行n步(相当于起点出发走n步,所以一定能到终点)。 + 每次用所有的m条边去松弛当前能到达的最短路(相当于每次从第n步骤的点出发走一下所有的边，更新到所有点的最短路)。 */ #include typedef long long LL; using namespace std; const int maxn = 510, maxm = 1e5+10; struct Edge{int u, v, w;}e[maxm]; int dist[maxn], tmp[maxn]; int main(){ int n, m, k; cin>>n>>m>>k; for(int i = 1; i <= m; i++) cin>>e[i].u>>e[i].v>>e[i].w; memset(dist,0x3f,sizeof(dist)); dist[1] = 0; for(int i = 1; i <= k; i++){ memcpy(tmp,dist,sizeof(dist)); for(int j = 1; j <= m; j++){ dist[e[j].v] = min(dist[e[j].v], tmp[e[j].u]+e[j].w); } } if(dist[n]>dist[505]/2)cout<<"impossible\n";//考虑存在边(x,n)但是没有边(1,x),用(x,n)更新(1,n)的距离后会使得(1,n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
AcWing 851. spfa求最短路
/* 给定一张有向/无向图,求s到所有点的最短路。 对于每个点i,我们记f[i]表示目前s到i的最短路,初始时为正无穷。 初始时将s加入队列,每次取出队首元素,用它更新别的点的f值。如果一个点的f值变小了并且它不在队列中,就将它加入队列。队列为空时结束。 如果不存在负权环,那么每个点最多加入队列n-1次。 */ #include #include #include using namespace std; const int maxn = 1e5+10; const int maxm = 1e5+10; //Grape int n, m; struct Edge{int v, w, next;}e[maxm<<1]; int tot, head[maxn]; void AddEdge(int u, int v, int w){ tot++; e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot; } //SPFA int dist[maxn], book[maxn];//book[i]表示当前i是否在队列中 queueq; void spfa(){ for(int i = 0; i <= n; i++)dist[i]=2147483647; dist[1]=0; book[1]=1; q.push(1); while(q.size()){ int u = q.front(); q.pop(); book[u]=0; for(int i = head[u]; i > 0; i = e[i].next){ int v = e[i].v, w = e[i].w; if(dist[v]>dist[u]+w){ dist[v] = dist[u]+w; if(!book[v]){ book[v] = 1; q.push(v); } } } } } int main(){ cin>>n>>m; for(int i = 1; i <= m; i++){ int x, y, z; cin>>x>>y>>z; AddEdge(x,y,z); } spfa(); if(dist[n]>dist[0]/2)cout<<"impossible\n"; else cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
AcWing 852. spfa判断负环
//cnt[i]表示编号为i的节点是第几个加入路径的节点 #include #include #include using namespace std; const int maxn = 2e3+10; const int maxm = 1e5+10; //Grape int n, m; struct Edge{int v, w, next;}e[maxm<<1]; int tot, head[maxn]; void AddEdge(int u, int v, int w){ tot++; e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot; } //SPFA int dist[maxn], book[maxn], cnt[maxn]; queueq; bool spfa(){ memset(dist,0x3f,sizeof(dist)); for(int i = 1; i <= n; i++){ q.push(i); book[i]=1;} while(q.size()){ int u = q.front(); q.pop(); book[u]=0; for(int i = head[u]; i > 0; i = e[i].next){ int v = e[i].v, w = e[i].w; if(dist[v]>dist[u]+w){ dist[v] = dist[u]+w; cnt[v] = cnt[u]+1; if(cnt[v]>n-1)return true; if(!book[v]){ book[v] = 1; q.push(v); } } } } return false; } int main(){ cin>>n>>m; for(int i = 1; i <= m; i++){ int x, y, z; cin>>x>>y>>z; AddEdge(x,y,z); } if(spfa())cout<<"Yes\n"; else cout<<"No\n"; return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
AcWing 854. Floyd求最短路
#include using namespace std; const int maxn = 210; int e[maxn][maxn]; int main(){ int n, m, q; cin>>n>>m>>q; memset(e,0x3f,sizeof(e)); for(int i = 1; i <= n; i++)e[i][i]=0; for(int i = 1; i <= m; i++){ int x, y, z; cin>>x>>y>>z; e[x][y] = min(e[x][y], z); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) e[i][j]=min(e[i][j],e[i][k]+e[k][j]); for(int i = 1; i <= q; i++){ int x,y; cin>>x>>y; if(e[x][y]>e[201][201]/2)cout<<"impossible\n"; else cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
AcWing 858. Prim算法求最小生成树
/* Prim: dist[i]维护节点i到生成树集合S的最短距离，每次找到最近的加入生成树，然后用该节点的所有直接相连边的更新生成树外的点到生成树的距离。 */ #include using namespace std; const int maxn = 550, inf=0x3f3f3f3f; int n, m, e[maxn][maxn]; int dist[maxn], vis[maxn]; int prim(){ for(int i = 1; i <= n; i++)dist[i] = e[1][i]; vis[1] = 1; int ans = 0; for(int i = 2; i <= n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!vis[j] && (t==-1||dist[t]>dist[j])){ t = j; } } if(dist[t] == inf)return inf; ans += dist[t]; vis[t] = 1; for(int j = 1; j <= n; j++) dist[j] = min(dist[j], e[t][j]); } return ans; } int main(){ cin>>n>>m; memset(e,0x3f,sizeof(e)); for(int i = 1; i <= n; i++)e[i][i] = 0; for(int i = 1; i <= m; i++){ int u, v, w; cin>>u>>v>>w; e[u][v] = e[v][u] = min(e[u][v],w); } int t = prim(); if(t==inf)cout<<"impossible\n"; else cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
AcWing 859. Kruskal算法求最小生成树
#include using namespace std; const int maxn = 2e5+10; struct node{int u, v, w; }e[maxn]; bool cmp(node a, node b){return a.w>n>>m; for(int i = 1; i <= m; i++){ cin>>e[i].u>>e[i].v>>e[i].w; } sort(e+1,e+m+1,cmp); int ans = 0, cnt = 0; init(n); for(int i = 1; i <= m; i++){ if(find(e[i].u)!=find(e[i].v)){ merge(e[i].u,e[i].v); ans += e[i].w; cnt++; } } if(cnt==n-1)cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
AcWing 860. 染色法判定二分图
/* 二分图染色： + 将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图 + dfs遍历所有点，每次将未染色的点进行染色，如果存在相邻两个点颜色相同就不是而二分图。 */ #include using namespace std; const int maxn = 2e5+10; vectorG[maxn]; int col[maxn]; int dfs(int u, int color){ col[u] = color; for(int v:G[u]){ if(!col[v]){ if(!dfs(v,3-color))return false; }else{ if(col[u]==col[v])return false; } } return true; } int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= m; i++){ int x, y; cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } int ok = 1; for(int i = 1; i <= n; i++){ if(!col[i]){ if(!dfs(i,1)){ ok = 0; break; } } } if(ok==1)cout<<"Yes\n"; else cout<<"No\n"; return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
AcWing 861. 二分图的最大匹配
#include #include #include using namespace std; const int N = 550; vectorG[N]; int po[N], book[N], ans;//po[v]表示点v当前的匹配对象。 int find(int u){ for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; if(!book[v]){//不在交替路中 book[v] = 1;//放入交替路 if(po[v]==0||find(po[v])){//当前点未用或最终未用，交替路是增广路。 po[v] = u;//匹配成功 return true; } } } return false; } int main(){ int nl, nr, m; cin>>nl>>nr>>m; for(int i = 1; i <= m; i++){ int x, y; cin>>x>>y; G[y].push_back(x); } for(int i = 1; i <= nr; i++){ memset(book,0,sizeof(book)); if(find(i)){ ans++; } } cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
电商家电数码
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
