前言
今天闲来无事,又写了一个beamer
其中略去了几乎所有证明,只保留了算法
感觉还是挺好懂的吧
参考例题:http://uoj.ac/problem/79
参考代码:
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 501; const int MOD = 998244353; int n,m; class Maximum_Matchings_in_General_Graph{ int a[N][N],b[N][N],G[N][N]; int tot,pat[N],id[N],num[N]; bool del_x[N],del_y[N]; public: inline void Add_Edge(int u, int v) { G[u][v] = a[u][v] = rand() % (MOD - 1) + 1; G[v][u] = a[v][u] = -a[u][v]; } inline int solve() { for (int i=1;i<=n;i++) id[i] = i; Gauss(n); for (int i=1;i<=n;i++) if (a[id[i]][id[i]]) num[++tot] = i; for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) a[i][j] = G[num[i]][num[j]]; Gauss(tot, 1); for (int i=1;i<=tot;i++) { if (!del_x[i]) { for (int j=1;j<=tot;j++) { if (!del_x[j] && G[num[i]][num[j]] && b[i][j]) { pat[num[i]] = num[j]; pat[num[j]] = num[i]; Eliminat(i, j); Eliminat(j, i); break; } } } } return tot; } inline void print() { printf("%d\n",tot>>1); for (int i=1;i<=n;i++) printf("%d ",pat[i]); } private: inline int Pow(int w, int t) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%MOD) if (t & 1) ret = (LL)ret * w % MOD; return ret; } inline void Gauss(int sz, bool I = 0) { for (int i=1;i<=sz;++i) b[i][i] = 1; for (int i=1;i<=sz;++i) { for (int j=i;j<=sz;++j) { if (a[j][i]) { swap(id[i], id[j]); swap(a[i], a[j]); if (I) swap(b[i], b[j]); break; } } if (!a[i][i]) continue; int inv = Pow(a[i][i], MOD - 2); for (int j=1;j<=sz;++j) if (a[i][j]) a[i][j] = (LL)a[i][j] * inv % MOD; if (I) for (int j=1;j<=sz;++j) if (b[i][j]) b[i][j] = (LL)b[i][j] * inv % MOD; for (int j=1;j<=sz;++j) { if (j != i && a[j][i]) { LL tmp = a[j][i]; for (int k=1;k<=sz;++k) if (a[i][k]) a[j][k] = (a[j][k] - tmp * a[i][k]) % MOD; if (I) for (int k=1;k<=sz;++k) if (b[i][k]) b[j][k] = (b[j][k] - tmp * b[i][k]) % MOD; } } } } inline void Eliminat(int x, int y) { del_x[x] = del_y[y] = 1; LL inv = Pow(b[x][y], MOD - 2); for (int i=1;i<=tot;++i) { if (!del_y[i]) { LL tmp = b[x][i] * inv % MOD; for (int j=1;j<=tot;++j) { if (!del_x[j] && b[y][j]) { b[i][j] = (b[i][j] - tmp * b[y][j]) % MOD; } } } } } }MMGG; inline char Read(){ static const int BUF_SIZE = 1000000; static char buf[BUF_SIZE],*p1=0,*p2=0; if (p1 == p2){ p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin); if (p2==p1) return -1; } return *p1++; } inline int read(){ char c=Read(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();} return ret*f; } int main() { srand(19260817); n = read(); m = read(); for (int i=1,u,v;i<=m;i++) { u = read(); v = read(); MMGG.Add_Edge(u, v); } MMGG.solve(); MMGG.print(); return 0; }
题目传送门:http://acm.timus.ru/problem.aspx?space=1&num=1099
离线版题目:http://paste.ubuntu.com/19164744/
一般图匹配的板题
然而抄范大神的代码抄错了,调了一个下午QAQ
详细情况见之后的博文吧,会单独写一篇算法笔记的
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 1000000; int n,match[MAXN],fa[MAXN],que[MAXN],fro,bak; int next[MAXN],mark[MAXN],vis[MAXN]; int T,nxt[MAXN],head[MAXN],to[MAXN]; inline int find(int w){ int f = fa[w], tmp; while (f != fa[f]) f = fa[f]; while (w != f) tmp=fa[w], fa[w]=f, w=tmp; return f; } inline void merge(int a, int b){ int f1 = find(a), f2 = find(b); if (f1 != f2) fa[f1] = f2; } inline int LCA(int x, int y){ static int t = 0; t++; while (true){ if (x) { x = find(x); if (vis[x] == t) return x; else { vis[x] = t; x = next[match[x]]; } } swap(x, y); } } inline void gather(int a, int p){ while (a != p){ int b = match[a], c = next[b]; if (find(c) != p) next = b; if (mark[b] == 2) mark[que[++fro]=b] = 1; if (mark == 2) mark[que[++fro]=c] = 1; merge(a, b); merge(b, c); a = c; } } inline void Augment(int s){ for (int i=1;i<=n;i++) next[i]=mark[i]=vis[i]=0, fa[i]=i; mark[s] = 1; que[fro=bak=1] = s; while (bak <= fro) { int w = que[bak++]; for (int i=head[w];i;i=nxt[i]){ if (match[w] == to[i]) continue; else if (find(to[i]) == find(w)) continue; else if (mark[to[i]] == 2) continue; else if (mark[to[i]] == 1) { int lca = LCA(w, to[i]); if (find(w) != lca) next[w] = to[i]; if (find(to[i]) != lca) next[to[i]] = w; gather(w, lca); gather(to[i], lca); } else if (!match[to[i]]) { next[to[i]] = w; for (int u=to[i]; u; ) { int v = next[u]; int fv = match[v]; match[v] = u; match[u] = v; u = fv; } return; } else { next[to[i]] = w; mark[que[++fro] = match[to[i]]] = 1; mark[to[i]] = 2; } } } } inline void AddEdge(int a, int b){ to[++T] = b; nxt[T] = head[a]; head[a] = T; to[++T] = a; nxt[T] = head[b]; head[b] = T; } int main(){ scanf("%d",&n); int a,b; while (~scanf("%d%d",&a,&b)) AddEdge(a, b); for (int i=1;i<=n;i++) if (!match[i]) Augment(i); int vout = 0; for (int i=1;i<=n;i++) if (match[i]) vout++; printf("%d\n",vout); for (int i=1;i<=n;i++) if (match[i] > i) printf("%d %d\n",i,match[i]); return 0; }
另外,此题有坑QAQ
边数巨多,TM还不告诉你是RE,给你说的是TLEQAQ