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小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
