#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int N = 250; // 并查集維護(hù) int belong[N]; int findb(int x) {return belong[x] == x ? x : belong[x] = findb(belong[x]); } void unit(int a, int b) {a = findb(a);b = findb(b);if (a != b) belong[a] = b; }int n, match[N]; vector<int> e[N]; int Q[N], rear; int _next[N], mark[N], vis[N]; // 樸素算法求某階段中搜索樹上兩點(diǎn)x, y的最近公共祖先r int LCA(int x, int y) {static int t = 0; t++;while (true) {if (x != -1) {x = findb(x); // 點(diǎn)要對(duì)應(yīng)到對(duì)應(yīng)的花上去 if (vis[x] == t)return x;vis[x] = t;if (match[x] != -1)x = _next[match[x]];else x = -1;}swap(x, y);} }void group(int a, int p) {while (a != p) {int b = match[a], c = _next[b];// _next數(shù)組是用來標(biāo)記花朵中的路徑的，綜合match數(shù)組來用，實(shí)際上形成了 // 雙向鏈表，如(x, y)是匹配的，_next[x]和_next[y]就可以指兩個(gè)方向了。 if (findb(c) != p) _next[c] = b;// 奇環(huán)中的點(diǎn)都有機(jī)會(huì)向環(huán)外找到匹配，所以都要標(biāo)記成S型點(diǎn)加到隊(duì)列中去， // 因環(huán)內(nèi)的匹配數(shù)已飽和，因此這些點(diǎn)最多只允許匹配成功一個(gè)點(diǎn)，在aug中 // 每次匹配到一個(gè)點(diǎn)就break終止了當(dāng)前階段的搜索，并且下階段的標(biāo)記是重 // 新來過的，這樣做就是為了保證這一點(diǎn)。 if (mark[b] == 2) mark[Q[rear++] = b] = 1;if (mark[c] == 2) mark[Q[rear++] = c] = 1;unit(a, b); unit(b, c);a = c;} }// 增廣 void aug(int s) {for (int i = 0; i < n; i++) // 每個(gè)階段都要重新標(biāo)記 _next[i] = -1, belong[i] = i, mark[i] = 0, vis[i] = -1;mark[s] = 1;Q[0] = s; rear = 1;for (int front = 0; match[s] == -1 && front < rear; front++) {int x = Q[front]; // 隊(duì)列Q中的點(diǎn)都是S型的 for (int i = 0; i < (int)e[x].size(); i++) {int y = e[x][i];if (match[x] == y) continue; // x與y已匹配，忽略 if (findb(x) == findb(y)) continue; // x與y同在一朵花，忽略 if (mark[y] == 2) continue; // y是T型點(diǎn)，忽略 if (mark[y] == 1) { // y是S型點(diǎn)，奇環(huán)縮點(diǎn) int r = LCA(x, y); // r為從i和j到s的路徑上的第一個(gè)公共節(jié)點(diǎn) if (findb(x) != r) _next[x] = y; // r和x不在同一個(gè)花朵，_next標(biāo)記花朵內(nèi)路徑 if (findb(y) != r) _next[y] = x; // r和y不在同一個(gè)花朵，_next標(biāo)記花朵內(nèi)路徑 // 將整個(gè)r -- x - y --- r的奇環(huán)縮成點(diǎn)，r作為這個(gè)環(huán)的標(biāo)記節(jié)點(diǎn)，相當(dāng)于論文中的超級(jí)節(jié)點(diǎn) group(x, r); // 縮路徑r --- x為點(diǎn) group(y, r); // 縮路徑r --- y為點(diǎn) }else if (match[y] == -1) { // y自由，可以增廣，R12規(guī)則處理 _next[y] = x;for (int u = y; u != -1; ) { // 交叉鏈取反 int v = _next[u];int mv = match[v];match[v] = u, match[u] = v;u = mv;}break; // 搜索成功，退出循環(huán)將進(jìn)入下一階段 }else { // 當(dāng)前搜索的交叉鏈+y+match[y]形成新的交叉鏈，將match[y]加入隊(duì)列作為待搜節(jié)點(diǎn) _next[y] = x;mark[Q[rear++] = match[y]] = 1; // match[y]也是S型的 mark[y] = 2; // y標(biāo)記成T型 }}} }bool g[N][N]; int main() {scanf("%d", &n);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) g[i][j] = false;// 建圖，雙向邊 int x, y; while (scanf("%d%d", &x, &y) != EOF) {x--, y--;if (x != y && !g[x][y])e[x].push_back(y), e[y].push_back(x);g[x][y] = g[y][x] = true;}// 增廣匹配 for (int i = 0; i < n; i++) match[i] = -1;for (int i = 0; i < n; i++) if (match[i] == -1) aug(i);// 輸出答案 int tot = 0;for (int i = 0; i < n; i++) if (match[i] != -1) tot++;printf("%d\n", tot);for (int i = 0; i < n; i++) if (match[i] > i)printf("%d %d\n", i + 1, match[i] + 1);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的图论--一般图带花树匹配--模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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