單鏈表

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10;// head 表示頭結點的下標 // e[i] 表示節(jié)點i的值 // ne[i] 表示節(jié)點i的next指針是多少 // idx 存儲當前已經(jīng)用到了哪個點 int head, e[N], ne[N], idx;// 初始化 void init() {head = -1;idx = 0; }// 將x插到頭結點 void add_to_head(int x) {e[idx] = x, ne[idx] = head, head = idx ++ ; }// 將x插到下標是k的點后面 void add(int k, int x) {e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ; }// 將下標是k的點后面的點刪掉 void remove(int k) {ne[k] = ne[ne[k]]; }int main() {int m;cin >> m;init(); // 初始化while (m -- ){int k, x;char op;cin >> op;if (op == 'H'){cin >> x;add_to_head(x);}else if (op == 'D'){cin >> k;if (!k) head = ne[head];else remove(k - 1);}else{cin >> k >> x;add(k - 1, x);}}for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";cout << endl;return 0; }

雙鏈表

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10;int idx, l[N], r[N], e[N];//在節(jié)點a的右邊插入x void insert(int a, int x) {e[idx] = x;l[idx] = a, r[idx] = r[a];l[r[a]] = idx, r[a] = idx ++ ; }//刪除節(jié)點a void remove(int a) {r[l[a]] = r[a];l[r[a]] = l[a]; }int main() {//0是左端點，1是右端點l[1] = 0, r[0] = 1, idx = 2;int m;cin >> m;while (m -- ){string op;int k, x;cin >> op;if (op == "L"){cin >> x;insert(0, x);}else if (op == "R"){cin >> x;insert(l[1], x);}else if (op == "D"){cin >> k;remove(k + 1);}else if (op == "IL"){cin >> k >> x;insert(l[k + 1], x);}else {cin >> k >> x;insert(k + 1, x);}}for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";return 0; }

樹與圖的深度優(yōu)先遍歷

樹的重心

• 樹是一種特殊的圖，無向圖又是特殊的有向圖；因此考慮有向圖如何存儲即可；有向圖的存儲 ：稠密圖->鄰接矩陣；鄰接表，存儲每個點可以到達哪些點
• 圖的鄰接表存儲方式是為每一個結點開個表，存的意思是從這個點可以走到哪些點，這個單鏈表內(nèi)部點的順序是無關緊要的
• n個點所以是n-1條邊；cstring頭文件；邊數(shù)這里設置為點數(shù)的兩倍，在開數(shù)組時注意；st數(shù)組記錄是否遍歷過該點，在遍歷一個點所有能到達的點的過程中，為了避免走回頭路，也要用到st數(shù)組；注意當前這顆子樹的大小 和 去掉這個點后最大聯(lián)通塊 之間的關系；圖用的是多條單鏈表，所以注意每次都要初始化h數(shù)組；無向圖，所以add兩次；這里隨便挑一個點都可以開始dfs，樹從哪個點都可以開始當根

#include <algorithm> #include <cstring> // memset #include <iostream>using namespace std;const int N = 1e5 + 10, M = 2 * N;int n, m;// head, e[M],ne[M],idx; 是一條單鏈表 // h[N], e[M],ne[M],idx; 是N條單鏈表 int h[N], e[M], ne[M], idx;bool st[N]; // 用st數(shù)組存一下哪些點已經(jīng)被遍歷過了int ans = N; //記錄一個全局最大值// 在a對應的單鏈表中插入一個節(jié)點b void add(int a, int b) {e[idx] = b; // 表示第idx條邊指向b點ne[idx] = h[a]; // ne[idx]表示第idx條邊的下一條邊是 a點的鄰接鏈表的第一條邊h[a] = idx++; // head[a]表示將a點的鄰接鏈表的第一條邊更新為第idx條邊 }// u表示當前已經(jīng)dfs到的這個點 // 以u為根的子樹中， 點的數(shù)量 int dfs(int u) {st[u] = true; // 標記一下， 當前這個點已經(jīng)被搜索過int sum = 1; // 記錄當前子樹大小int res = 0; // 把u這個點刪除之后， 每一個聯(lián)通塊的最大值for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i]; // 當前這個鏈表中的節(jié)點， 對應圖中的點的編號是多少if (!st[j]) {int s = dfs(j); // j這棵子樹的大小res = max(res, s); //最大的聯(lián)通塊大小sum += s;}}res = max(res, n - sum);ans = min(ans, res);return sum; }int main() {// 一條單鏈表 head初始化為-1// n條單鏈表，把所有的head初始化為-1memset(h, -1, sizeof h);cin >> n;for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;add(a, b);add(b, a);}// 隨便挑一個點， 比方說從第一個點開始搜dfs(1);cout << ans << endl;return 0; }

樹與圖的廣度優(yōu)先遍歷

圖中點的層次

• 建圖然后bfs；dist表示距離，-1表示走不到，初始化為-1

#include <iostream> #include <cstring> #include <queue>using namespace std;const int N = 1e5 + 10;int n, m; int h[N], e[N], ne[N], idx; int dist[N];void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx ++ ; }int bfs() {memset(dist, -1, sizeof dist);queue<int> q;q.push(1);dist[1] = 0;while (q.size()){auto t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] == -1){dist[j] = dist[t] + 1;q.push(j);}}}return dist[n]; }int main() {memset(h, -1, sizeof h);scanf("%d%d", &n, &m);for (int i = 0; i < m; i ++ ){int a, b;scanf("%d%d", &a, &b);add(a, b);}printf("%d\n", bfs()); }

拓撲排序

有向圖的拓撲序列

• 有向無環(huán)圖也被稱為拓撲圖
• 拓撲序列 ：所有的邊都從前指向后，那么所有入度為0的點都可以作為起點

#include <iostream> #include <cstring> #include <queue>using namespace std;const int N = 1e5 + 10;int h[N], e[N], ne[N], idx; int top[N]; int d[N]; int cnt = 0; int n, m;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }bool topsort() {queue<int> q;for (int i = 1; i <= n; i ++ )if (!d[i])q.push(i);while (q.size()){auto t = q.front();q.pop();top[cnt ++ ] = t;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j] -- ;if (!d[j])q.push(j);}}return cnt == 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);d[b] ++ ;}if (!topsort()) puts("-1");else{for (int i = 0; i < n; i ++ ){cout << top[i];if (i != n - 1) cout << ' ';}}return 0; } #include <iostream> #include <cstring>using namespace std;const int N = 1e5 + 10;int h[N], e[N], ne[N], idx; int q[N]; int d[N];int n, m;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 ++ )if (!d[i])q[ ++ tt] = i;while (hh <= tt){auto t = q[hh ++ ];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j] -- ;if (!d[j])q[ ++ tt] = j;}}return tt + 1 == n; }int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 0; i < m; i ++ ){int a, b;cin >> a >> b;add(a, b);d[b] ++ ;}if (!topsort()) puts("-1");else{for (int i = 0; i < n; i ++ ){cout << q[i];if (i != n - 1) cout << ' ';}}return 0; }

Dijkstra

Dijkstra求最短路 I

• 稠密圖，鄰接矩陣；稀疏圖，鄰接表
• 建圖時要把所有邊初始化為正無窮，，為了應對重邊，每次保留最短的邊；先將所有距離初始化為正無窮，起點距離為0，遍歷n-1輪，每輪確定一個點，找到未標記的點中距離最小的，然后用這個點更新其它點的距離，再標記這個距離最小的點，表示已經(jīng)用它更新過
• 每個點只能被用來更新其它點一次
• 基于貪心思想，只適用于所有邊的長度都是非負數(shù)的圖

#include <iostream> #include <cstring>using namespace std;const int N = 510;int g[N][N]; int dist[N]; bool st[N];int n, m;int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }int main() {memset(g, 0x3f, sizeof g);cin >> n >> m;for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c);}printf("%d", dijkstra());return 0; }

Dijkstra求最短路 II

• 稀疏圖 -> 鄰接表（相比多了w數(shù)組記錄權值
• 用鄰接表存圖，重邊無所謂
• priority_queue在queue頭文件中，小根堆默認按照第一個權值從小到大排序
• 小根堆的寫法
• 每次找全局最小且未被標記過的去更新其它點的dist；所以在每次更新的時候順便把新的dist和對應的點放進去
• 同上，每一個點只會被用來松弛其它邊一次，所以只會進優(yōu)先隊列一次；在松弛其它邊的時候，如果松弛成功，就將點進入優(yōu)先隊列

#include <algorithm> #include <cstring> #include <iostream> #include <queue>using namespace std;const int N = 1e6 + 10;typedef pair<int, int> pii;int n, m; int head[N], e[N], ne[N], idx, w[N]; int dist[N]; //從1號點走到每個點， 當前的最短距離是多少 bool st[N]; //用于在更新最短距離時，判斷當前的點的最短距離是否確定，是否需要更新void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = head[a];head[a] = idx++; }// 進行n次迭代后最后就可以確定每個點的最短距離 // 然后再根據(jù)題意輸出相應的 要求的最短距離 int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0; // 第一個點到自己的距離為0priority_queue<pii, vector<pii>, greater<pii>> heap; //轉換為小根堆heap.push({0, 1}); //將1號點放進來， 值是0， 編號是1while (heap.size()) {auto t = heap.top(); //每次找到堆中最小的點heap.pop();int ver = t.second, distance = t.first; //距離最小的點的編號和距離if (st[ver]) { //如果這個點被訪問過， 就continuecontinue;}st[ver] = true;// 更新當前這個點的所有出邊for (int i = head[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) { // 如果第n個點路徑為無窮大即不存在最低路徑return -1;}return dist[n]; }int main() {cin >> n >> m;memset(head, -1, sizeof head);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c); //用鄰接表存， 重邊就無所謂了}// 求單源最短路徑cout << dijkstra() << endl;return 0; }

bellman-ford

有邊數(shù)限制的最短路

• memcpy(last, dist, sizeof dist)中l(wèi)ast數(shù)組是上一輪中dist數(shù)組的備份，是為了防止串聯(lián)更新，因為bellmanford是求有邊數(shù)限制的最短路，而spfa是沒有邊數(shù)限制的，所以不需要拷貝上一輪。
• Bellman - ford 算法是求含負權圖的單源最短路徑的一種算法，效率較低，代碼難度較小。其原理為連續(xù)進行松弛，在每次松弛時把每條邊都更新一下，若在 n-1 次松弛后還能更新，則說明圖中有負環(huán)，因此無法得出結果，否則就完成。
• 在下面代碼中，是否能到達n號點的判斷中需要進行if(dist[n] > INF/2)判斷，而并非是if(dist[n] == INF)判斷，原因是INF是一個確定的值，并非真正的無窮大，會隨著其他數(shù)值而受到影響，dist[n]大于某個與INF相同數(shù)量級的數(shù)即可
• bellman - ford算法擅長解決有邊數(shù)限制的最短路問題，時間復雜度 O(nm)，其中n為點數(shù)，m為邊數(shù)
• 存邊方式獨特，邊數(shù)限制，拷貝上一輪，大于判斷

#include <algorithm> #include <cstring> #include <iostream>using namespace std;const int N = 510, M = 10010;struct Edge {int a, b, c; } edges[M];int n, m, k; int dist[N]; int last[N];void bellman_ford() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < k; i++) {memcpy(last, dist, sizeof dist); //只用上一次迭代的結果for (int j = 0; j < m; j++) {auto e = edges[j];dist[e.b] = min(dist[e.b], last[e.a] + e.c);}} }int main() {cin >> n >> m >> k;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;edges[i] = {a, b, c};}bellman_ford();if (dist[n] > 0x3f3f3f3f / 2) {cout << "impossible" << endl;}else {cout << dist[n] << endl;}return 0; }

spfa

spfa求最短路

• spfa被稱為隊列優(yōu)化的bellmanford算法，
• 建立一個隊列，最初隊列中只包含起點；取出隊頭x，掃描它的所有出邊（x，y，z），如果能被松弛，則松弛dist[y]，同時如果y不在隊列中，將y放入隊列中（每次取出隊頭的時候也要改變st數(shù)組）；
• 一個結點可能被入隊，出隊多次；這個隊列避免了bellmanford算法中對不需要拓展的結點的冗余掃描，在稀疏圖上運行效率較高，為$O(km)$級別，k是一個較小的常數(shù)，但在稠密圖或者特殊構造的網(wǎng)格圖上，仍可能退化成$O(nm)$
• st為true的點也可能被再次更新，所以更新的時候不需要判斷是否！st
• st數(shù)組記錄這個點當前是否在隊列中
• 隊列中都是由起點更新到的點，不存在bellmanford中未更新到的點同樣被邊更新的情況，所以spfa中等于判斷就可以，不像bellman中是大于判斷

#include <cstring> #include <iostream> #include <queue>using namespace std;const int N = 1e5 + 10;int n, m; int head[N], e[N], ne[N], w[N], idx; bool st[N]; int dist[N];void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = head[a];head[a] = idx++; }int spfa() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true; //判重數(shù)組， 隊列中有重復的點沒有意義while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = head[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() {cin >> n >> m;memset(head, -1, sizeof head);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}int t = spfa();if (t == -1) {cout << "impossible" << endl;}else {cout << dist[n] << endl;}return 0; }

spfa判斷負環(huán)

• dist和cnt數(shù)組都不需要被初始化，dist數(shù)組代表當前從1到x的最短路徑長度，cnt數(shù)組代表當前從1到x的邊的數(shù)量
• 一開始就把所有點都放到隊列里，只有在松弛的時候才會判斷如果不在隊列中再把它放入隊列中，如果松弛時發(fā)現(xiàn)cnt也就是邊數(shù)>=n，說明點大于n，說明有負權回路

#include <cstring> #include <iostream> #include <queue>using namespace std;const int N = 2e3 + 10, M = 1e4 + 10;int n, m; int head[N], e[M], ne[M], w[M], idx; bool st[N]; int dist[N]; // 表示 當前從1 -> x的最短距離 int cnt[N]; //cnt[x] 表示 當前從1 -> x的最短路的邊數(shù)void add(int a, int b, int c) {e[idx] = b;ne[idx] = head[a];w[idx] = c;head[a] = idx++; }bool spfa(){// 這里不需要初始化dist數(shù)組為 正無窮/初始化的原因是， 如果存在負環(huán)， 那么dist不管初始化為多少， 都會被更新queue<int> q;//不僅僅是1了， 因為點1可能到不了有負環(huán)的點， 因此把所有點都加入隊列for(int i=1;i<=n;i++){q.push(i);st[i]=true;}while(q.size()){int t = q.front();q.pop();st[t]=false;for(int i = head[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){ // 有n條邊，則n + 1個點，抽屜原理，有兩個點是同一個點，則說明路徑上存在環(huán)，又因為路徑變小，說明存在負環(huán)return true;}if(!st[j]){q.push(j);st[j]=true;}}}}return false; }int main() {cin >> n >> m;memset(head, -1, sizeof head);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}if (spfa()) {cout << "Yes" << endl;}else {cout << "No" << endl;}return 0; }

Floyd

Floyd求最短路

• D[k, i, j]表示“經(jīng)過若干個編號不超過k的結點“從i到j的最短路徑，該問題可劃分為兩個子問題，經(jīng)過編號不超過k-1的點從i到j，或者從i先到k再到j，$D[k,i,j]=min(D[k?1,i,j],D[k?1][i][k]+D[k?1][k][j])$，初值為$D[0,i,j]=A[i,j]$，其中A[i,j]是開頭定義的鄰接矩陣
• 與背包問題的狀態(tài)轉移方程類似，k這一維可被省略$D[i,j]=min(D[i,j],D[i][k]+D[k][j])$，最終D[i][j]就保存了從i到j的最短路長度

#include <algorithm> #include <cstring> #include <iostream>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, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c);}floyd();while (Q--) {int a, b;cin >> a >> b;int t = d[a][b];if (t > INF / 2) {cout << "impossible" << endl;}else {cout << t << endl;}}return 0; }

• floyd距離和鄰接矩陣中兩點之間邊的距離用的是同一個數(shù)組，
• 這里也可以用0x3f3f3f3f，之所以能用1e9應該是這里的總邊長才2e8
• 鄰接矩陣的初始化，這里多了個0，值得注意
• 這里仍然是判斷大于而不是判斷等于，也許還是因為不是從起點更新起的，

Prim

Prim算法求最小生成樹

• $O(n^2)$。堆優(yōu)化版也不如kruskal方便，所以Prim算法主要用于稠密圖，尤其是完全圖的最小生成樹的求解。
• Prim總是維護最小生成樹的一部分。最初，Prim算法僅確定1號節(jié)點屬于最小生成樹；把元素從剩余節(jié)點集合中刪除，加入到已經(jīng)屬于最小生成樹的節(jié)點集合中去，并把兩個端點分別屬于這兩個集合中的權值最小的點累加到答案中。
• 可以類別Dijkstra，用一個數(shù)組標記節(jié)點是否屬于集合T，每次從未標記的節(jié)點中選擇d值最小的，把它標記，同時掃描所有出邊，更新另一個端點的d值。

#include <iostream> #include <cstring>using namespace std;const int N = 510; const int INF = 0x3f3f3f3f;int g[N][N]; int dist[N]; bool st[N]; int n, m;int prim() {memset(dist, 0x3f, sizeof dist);int res = 0;dist[1] = 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) // 如果i為0不用return INF;st[t] = true; // 標記if (i) res += dist[t]; // 如果i為0不用累加for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], g[t][j]); // 是與g做比較，因為t已經(jīng)是最小生成樹里的了}// 返回累加答案return res; }int main() {cin >> n >> m;memset(g, 0x3f, sizeof g);while (m -- ){int u, v, w;cin >> u >> v >> w;g[u][v] = g[v][u] = min(g[u][v], w);}int t = prim();if (t == INF) puts("impossible");else cout << t << endl;return 0; }

Kruskal

Kruskal算法求最小生成樹

• 從邊帶權的無向圖中選n個點和n-1條本來就有的邊構成的無向連通子圖稱為生成樹，在此基礎上邊的權值之和最小的稱為最小生成樹
• 定理 ：任意一顆最小生成樹一定包含無向圖中權值最小的邊
• Kruskal算法總是維護無向圖的最小生成森林
• 在任意時刻，Kruskal算法從剩余的邊中選一條權值最小的，并且這條邊的兩個端點屬于生成森林中兩顆不同的樹（不連通），把該邊加入該森林。圖中節(jié)點的連通情況可以用并查集維護
• 流程 ：建立并查集；把所有邊按權值排序從小到大，依次掃描每條邊；若兩個端點屬于同一個集合，則忽略這條邊；否則，合并兩個端點所在的集合，并將權值累加到答案中
• 雖然Kruskal算法的時間復雜度局限在于它第一步要使用的庫里的快排，o(mlog(m))，但快排常數(shù)非常小，所以Kruskal很快

#include <iostream> #include <algorithm>using namespace std;const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f; int n, m; int fa[N];struct Edge {int a, b, w;bool operator< (const Edge &W) const{return w < W.w;} }edges[M];int find(int x) {if (fa[x] != x) fa[x] = find(fa[x]);return fa[x]; }int kruskai() {for (int i = 1; i <= n; i ++ ) fa[i] = i; // 初始化并查集int res = 0, cnt = 0;1for (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){res += w;cnt ++ ;fa[a] = b;}}if (cnt < n - 1) return INF;return res; }int main() {cin >> n >> m;for (int i = 0; i < m; i ++ )cin >> edges[i].a >> edges[i].b >> edges[i].w;sort(edges, edges + m); // 排序int t = kruskai();if (t == INF)puts("impossible");elsecout << t;return 0; }

染色法判定二分圖

染色法判定二分圖

• 二分圖 ：當且僅當圖中沒有奇數(shù)環(huán)，劃分為兩個集合，集合內(nèi)部沒有邊

#include <iostream> #include <algorithm> #include <cstring>using namespace std;const int N = 1e5 + 10, M = 2 * N; // 無向圖，邊存兩次，數(shù)組兩倍int h[N], e[M], ne[M], idx; int co[N]; int n, m;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }bool dfs(int u, int c) {co[u] = c;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!co[j] && !dfs(j, 3 - c))return false;else if (co[j] == c)return false;}return true; }int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 0; i < m; i ++ ){int u, v;cin >> u >> v;add(u, v);add(v, u); // 無向圖}bool success = true;for (int i = 1; i <= n; i ++ ) // 圖可能不連通if (!co[i] && !dfs(i, 1)){success = false;break;}if (success) puts("Yes");else puts("No");return 0; }

匈牙利算法

二分圖的最大匹配

• “任意兩條邊都沒有公共端點”的邊的集合被稱為圖的一組匹配。在二分圖中，包含邊數(shù)最多的一組匹配被稱為二分圖的最大匹配。
• 二分圖的一組匹配S是最大匹配，當且僅當圖中不再存在S的增廣路
  
• 匈牙利算法基于貪心思想，當一個點成為匹配點后，最多因為增廣路而更換匹配對象，不會再變回非匹配點
• 對于每個左部節(jié)點，尋找增廣路最多遍歷整張二分圖一次，所以$O(nm)$

#include <iostream> #include <cstring>using namespace std;const int N = 510, M = 1e5 + 10;int h[N], e[M], ne[M], idx; bool st[N]; // st數(shù)組代表對于當前左部節(jié)點，右部的這個節(jié)點在它這輪的匹配中是否被“詢問”過;在同一輪中不要重復詢問同一個點 int match[N]; int n1, n2, m;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;if (match[j] == 0 || find(match[j])){match[j] = x;return true;}}}return false; }int main() {memset(h, -1, sizeof h);cin >> n1 >> n2 >> m;for (int i = 0; i < m; i ++ ){int a, b;cin >> a >> b;add(a, b); // add(b, a); 從左部匹配右部，所以即使無向圖，加了會wa}int res = 0;for (int i = 1; i <= n1; i ++ ){memset(st, 0, sizeof st);if (find(i)) res ++ ;}cout << res << endl;return 0; }

總結

以上是生活随笔為你收集整理的AcWing算法基础课 Level-2 第三讲 搜索与图论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。