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

### PDF

maximum_matchings_via_gaussian_elimination

## 【模板库】一般图最大匹配

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

static const int BUF_SIZE = 1000000;
static char buf[BUF_SIZE],*p1=0,*p2=0;
if (p1 == p2){
if (p2==p1) return -1;
} return *p1++;
}

return ret*f;
}

int main() {
srand(19260817);
for (int i=1,u,v;i<=m;i++) {
}
MMGG.solve();
MMGG.print();
return 0;
}



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

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

## 【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){
}

int main(){
scanf("%d",&n); int a,b;