## 【算法笔记】基于线性代数的一般图匹配算法

### PDF

maximum_matchings_via_gaussian_elimination

## 【算法笔记】基于线性代数的一般图匹配算法

##### ★,°:.☆(￣▽￣)/\$:.°★ 。
maximum_matchings_via_gaussian_keynote

## 【NKOJ 2922】密码锁

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,m,k,cnt,dis[10010],sz[200],pos[30],f[1200000],cost[30][30];
queue<int> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void BFS(int W, int num) {
memset(dis,127,sizeof(dis));
que.push(W); dis[W] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=1;i<=m;i++) {
if (w+sz[i] <= n+1 && dis[w+sz[i]] > dis[w]+1)  dis[w+sz[i]] = dis[w]+1, que.push(w+sz[i]);
if (w-sz[i] >= 1 && dis[w-sz[i]] > dis[w]+1)  dis[w-sz[i]] = dis[w]+1, que.push(w-sz[i]);
}
}
for (int i=1;i<=cnt;i++) cost[num][i] = dis[pos[i]];
}

int main(){
for (int i=1;i<=k;i++) dis[read()] = 1;
for (int i=1;i<=m;i++) sz[i] = read(); sort(sz+1,sz+1+m); m = unique(sz+1,sz+1+m) - sz - 1;
for (int i=1;i<=n+1;i++) if (dis[i] + dis[i-1] == 1) pos[++cnt] = i;
for (int i=1;i<=cnt;i++) BFS(pos[i],i);
memset(f,127,sizeof(f));
f[(1<<cnt)-1] = 0;
for (int w=(1<<cnt)-1;w;w--) if (f[w] < 1e9)
for (int i=1;i<=cnt;i++) if (w&(1<<i-1)) for (int j=i+1;j<=cnt;j++) if (w&(1<<j-1) && cost[i][j] < 1e9)
f[w^(1<<i-1)^(1<<j-1)] = min(f[w^(1<<i-1)^(1<<j-1)],f[w]+cost[i][j]);
printf("%d\n",f[0]>1e9?-1:f[0]);
return 0;
}

## 【Timus 1099】Work Scheduling

#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];

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++];
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;
}