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

参考例题: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;
}

【Timus 1099】Work Scheduling

题目传送门: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