一般图最大匹配——带花树模板
偶然碰到这个算法，学习下。
这样可以在O(n^3)的时间内找出非二分图的最大匹配。
#include <cstdio> #include <algorithm> #include <set> #include <vector> using namespace std; const int NMax=401; int Next[NMax]; int spouse[NMax]; int belong[NMax]; int findb(int a){ return belong[a]==a?a:belong[a]=findb(belong[a]); } void together(int a,int b){ a=findb(a),b=findb(b); if (a!=b)belong[a]=b; } vector<int> E[NMax]; int N; int Q[NMax],bot; int mark[NMax]; int visited[NMax]; int findLCA(int x,int y){ static int t=0; t++; while (1){ if (x!=-1){ x=findb(x); if (visited[x]==t)return x; visited[x]=t; if (spouse[x]!=-1)x=Next[spouse[x]]; else x=-1; } swap(x,y); } } void goup(int a,int p){ while (a!=p){ int b=spouse[a],c=Next[b]; if (findb(c)!=p)Next[c]=b; if (mark[b]==2)mark[Q[bot++]=b]=1; if (mark[c]==2)mark[Q[bot++]=c]=1; together(a,b); together(b,c); a=c; } } void findaugment(int s){ for (int i=0;i<N;i++)Next[i]=-1,belong[i]=i,mark[i]=0,visited[i]=-1; Q[0]=s;bot=1;mark[s]=1; for (int head=0;spouse[s]==-1 && head<bot;head++){ int x=Q[head]; for (int i=0;i<(int)E[x].size();i++){ int y=E[x][i]; if (spouse[x]!=y && findb(x)!=findb(y) && mark[y]!=2){ if (mark[y]==1){ int p=findLCA(x,y); if (findb(x)!=p)Next[x]=y; if (findb(y)!=p)Next[y]=x; goup(x,p); goup(y,p); }else if (spouse[y]==-1){ Next[y]=x; for (int j=y;j!=-1;){ int k=Next[j]; int l=spouse[k]; spouse[j]=k;spouse[k]=j; j=l; } break; }else{ Next[y]=x; mark[Q[bot++]=spouse[y]]=1; mark[y]=2; } } } } } int Map[NMax][NMax]; void init(int N) { for (int i=0;i<N;i++) { E[i].clear(); for (int j=0;j<N;j++) { Map[i][j]=0; } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&N);//输入点的个数 init(N); // 然后添加边即可。 /* Map[i][j]=Map[j][i]=1; E[i].push_back(j); E[j].push_back(i); */ for (int i=0;i<N;i++)spouse[i]=-1; for (int i=0;i<N;i++)if (spouse[i]==-1) findaugment(i); int ret=0; for (int i=0;i<N;i++)if (spouse[i]!=-1)ret++; printf("%d\n",ret/2); // for (int i=0;i<N;i++) // if (spouse[i]!=-1 && spouse[i]>i) // printf("%d %d\n",i+1,spouse[i]+1); } return 0; }
//以防万一，再带一个模板。
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int N = 250; // 并查集维护 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]; // 朴素算法求某阶段中搜索树上两点x, y的最近公共祖先r int LCA(int x, int y) { static int t = 0; t++; while (true) { if (x != -1) { x = findb(x); // 点要对应到对应的花上去 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数组是用来标记花朵中的路径的，综合match数组来用，实际上形成了 // 双向链表，如(x, y)是匹配的，next[x]和next[y]就可以指两个方向了。 if (findb(c) != p) next[c] = b; // 奇环中的点都有机会向环外找到匹配，所以都要标记成S型点加到队列中去， // 因环内的匹配数已饱和，因此这些点最多只允许匹配成功一个点，在aug中 // 每次匹配到一个点就break终止了当前阶段的搜索，并且下阶段的标记是重 // 新来过的，这样做就是为了保证这一点。 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++) // 每个阶段都要重新标记 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]; // 队列Q中的点都是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型点，忽略 if (mark[y] == 1) { // y是S型点，奇环缩点 int r = LCA(x, y); // r为从i和j到s的路径上的第一个公共节点 if (findb(x) != r) next[x] = y; // r和x不在同一个花朵，next标记花朵内路径 if (findb(y) != r) next[y] = x; // r和y不在同一个花朵，next标记花朵内路径 // 将整个r -- x - y --- r的奇环缩成点，r作为这个环的标记节点，相当于论文中的超级节点 group(x, r); // 缩路径r --- x为点 group(y, r); // 缩路径r --- y为点 } else if (match[y] == -1) { // y自由，可以增广，R12规则处理 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; // 搜索成功，退出循环将进入下一阶段 } else { // 当前搜索的交叉链+y+match[y]形成新的交叉链，将match[y]加入队列作为待搜节点 next[y] = x; mark[Q[rear++] = match[y]] = 1; // match[y]也是S型的 mark[y] = 2; // y标记成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; }优质内容筛选与推荐>>
1、记录一次CDH集群邮件报警功能的设置
2、《大道至简七八章》
3、在Linux(CenterOS7)系统中查看Tomcat进程
4、[笔记] Windows Presentation Foundation Data Binding: Part 1（WPF中的数据邦定1）
5、LIS（最长上升子序列）