一般图的最大匹配
带花树算法
配套食用：
ljh2000-jumpOI界第一麻瓜论文作者: vfleaking
详细讲解: yihuikang
这里有一道范围 1 e 4 1e4 1e4的非常有意思的一般图最大权匹配的题，老板们可以去艹一艹这道题：winter camp day8 div2 B题
UOJ79模板
//75ms #include <bits/stdc++.h> using namespace std; typedef long long LL; inline int getint() { int w = 0, q = 0; char c = getchar(); while ((c < '0' || c > '9') && c != '-') c = getchar(); if (c == '-') q = 1, c = getchar(); while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar(); return q ? -w : w; } class Dhs { public: static const int D_MXN = 520; static const int D_MXE = 300005; static const int D_MXQL = 10005; int n, m; int eCnt, head[D_MXN], nex[D_MXE], to[D_MXE]; int dui[D_MXQL], hed, tail; int fa[D_MXN], id[D_MXN], pre[D_MXN], match[D_MXN], vis[D_MXN], Tim; inline void add_edge(int u, int v) { nex[++eCnt] = head[u]; to[eCnt] = v; head[u] = eCnt; } inline int Fi(int x) { if (fa[x] != x) fa[x] = Fi(fa[x]); return fa[x]; } inline int lca(int x, int y) { Tim++; while (vis[x] != Tim) { if (x) { x = Fi(x); if (vis[x] == Tim) return x; vis[x] = Tim; if (match[x] != 0) x = Fi(pre[match[x]]); else x = 0; } swap(x, y); } return x; } inline void change(int x, int y, int k) { //把奇环上的点缩成一个点，并且把原来是奇点的点变成偶点，加入队列 while (Fi(x) != k) { pre[x] = y; int z = match[x]; if (id[z] == 1) { id[z] = 0; dui[++tail] = z; } if (Fi(z) == z) fa[z] = k; if (Fi(x) == x) fa[x] = k; y = z; x = pre[y]; } } inline bool bfs(int ini) { for (int i = 1; i <= n; i++) id[i] = -1, fa[i] = i; hed = tail = 0; dui[++tail] = ini; id[ini] = 0; int u; while (hed < tail) { u = dui[++hed]; for (int i = head[u]; i; i = nex[i]) { int v = to[i]; if (id[v] == -1) { pre[v] = u; id[v] = 1; if (!match[v]) { int last, t, now = v; while (now != 0) { t = pre[now]; last = match[t]; match[t] = now; match[now] = t; now = last; } return true; } id[match[v]] = 0; dui[++tail] = match[v]; } else if (id[v] == 0 && Fi(u) != Fi(v)) { //出现奇环且不是在同一个环中 int g = lca(u, v); change(u, v, g); change(v, u, g); } } } return false; } void init() { eCnt = Tim = 0; for (int i = 0; i <= 500; ++i) assert(head[i] == 0 && match[i] == 0 && vis[i] == 0 && pre[i] == 0); } inline void work() { init(); n = getint(); m = getint(); int x, y; for (int i = 1; i <= m; i++) { x = getint(); y = getint(); add_edge(x, y); add_edge(y, x); } int ans = 0; for (int i = 1; i <= n; i++) if (!match[i] && bfs(i)) ans++; printf("%dn", ans); for (int i = 1; i <= n; i++) printf("%d ", match[i]); puts(""); } } dhs; int main() { dhs.work(); system("pause"); return 0; } //74ms //https://www.cnblogs.com/owenyu/p/6858508.html #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=505; const int maxm=maxn*maxn*2; int n,m,que[maxm],ql,qr,pre[maxn],tim=0; struct edge { int v,nxt; } e[maxm]; int h[maxn],tot=0; int match[maxn],f[maxn],tp[maxn],tic[maxn]; int find(int x) { return f[x]==x?f[x]:f[x]=find(f[x]); } void add(int u,int v) { e[++tot]=(edge){v,h[u]}; h[u]=tot; } int lca(int x,int y) { for (++tim;;swap(x,y)) if (x) { x=find(x); if (tic[x]==tim) return x; else tic[x]=tim,x=pre[match[x]]; } } void shrink(int x,int y,int p) { while (find(x)!=p) { pre[x]=y,y=match[x]; if (tp[y]==2) tp[y]=1,que[++qr]=y; if (find(x)==x) f[x]=p; if (find(y)==y) f[y]=p; x=pre[y]; } } bool aug(int s) { for (int i=1;i<=n;++i) f[i]=i; memset(tp,0,sizeof tp),memset(pre,0,sizeof pre); tp[que[ql=qr=1]=s]=1; // 1: type A ; 2: type B int t=0; while (ql<=qr) { int x=que[ql++]; for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) { if (find(v)==find(x) || tp[v]==2) continue; if (!tp[v]) { tp[v]=2,pre[v]=x; if (!match[v]) { for (int now=v,last,tmp;now;now=last) { last=match[tmp=pre[now]]; match[now]=tmp,match[tmp]=now; } return true; } tp[match[v]]=1,que[++qr]=match[v]; } else if (tp[v]==1) { int l=lca(x,v); shrink(x,v,l); shrink(v,x,l); } } } return false; } int main() { n=read(),m=read(); for (int i=1;i<=m;++i) { int x=read(),y=read(); add(x,y),add(y,x); } int ans=0; for (int i=1;i<=n;++i) ans+=(!match[i] && aug(i)); printf("%dn",ans); for (int i=1;i<=n;++i) printf("%d ",match[i]); puts(""); return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215题目
14多校9B题,HDU4687 Boke and Tsukkomi timus1099传送门
zoj 3316 Game题意： 棋盘上有一些棋子，两位选手轮流移除棋子，后者移除的棋子和前者移动的棋子 曼哈顿距离之差不能小于L。不能移除棋子者输。问后手是否能赢？
解题思路： 能连续移除棋子之间连一条边，求一般图最大匹配M。若M * 2 = N,后手胜
题意: 棋盘上有个king 可以往周围20个合法地方移动。给出棋盘，某些位置不能移到。 两位选手轮流移动king，不能移动到先前到达过的位置，不能移动者输。问先手是否能赢？
解题思路：能够合法相互移动的位置连边。将起点去掉，求一般图最大匹配。将起点加入， 寻找可增广路，若存在可增广路，则先手胜。（求两次最大图匹配也行）
题意: 给出一个无向图，存在重边，没有自环。问能否删除一些边，使得每个顶点的度数为， 指定度数deg[i]？
解题思路1： 我们应该删除哪些边呢？ 预处理每个顶点的度数d[i], 若d[i] = deg[i], 那么 与这个点相连的边是不能删掉的。原因很显然。若i与j之间有边，并且d[i]>deg[i], d[j]>deg[j]那么这条边是可以删除的。接下来如何建图呢？ 将每个点i 拆成 d[i] - deg[i]个点。如果i与j之间的边e可以删除, 则边e与i、j拆出的每个点连一条边 ei, ej（重边连多次）。然后求该一般图最大匹配，若存在完美匹配，则YES。
解题思路2：
把一条边拆成两个点，把每个点u拆成du[u]个点
edge ->e1 e2
x -> x1
y -> y1 y2
(e1, e2), (x1, e1), (e2, y1), (e2, y2)
再跑一般图最大匹配
看是否是完备匹配
如果存在完美匹配的话，一定可以是每条边拆成两个点分别和两个端点拆成
的du[i]个点中的一个相匹配。
如果完备匹配的话，证明说有条件都满足。
如果du[i]等于任意0或者整数, 也是可以这样写的
如果du[i]等于0的话，相当于i相邻的边拆成的两个点自己和自己相匹配
/* 链接 https://ac.nowcoder.com/acm/contest/5666/I 题意 n=50 m=100 小明要求每个点的度数为 du[i] = 1 or 2, 问你是否存在这样一个边的子集 满足上述条件。 不存在自环，可能有重边 思路 把一条边拆成两个点，把每个点u拆成du[u]个点 edge ->e1 e2 x -> x1 y -> y1 y2 (e1, e2), (x1, e1), (e2, y1), (e2, y2) 再跑一般图最大匹配 看是否是完备匹配 如果存在完美匹配的话，一定可以是每条边拆成两个点分别和两个端点拆成 的du[i]个点中的一个相匹配。 如果完备匹配的话，证明说有条件都满足。 备注 如果du[i]等于任意0或者整数, 也是可以这样写的 如果du[i]等于0的话，相当于i相邻的边拆成的两个点自己和自己相匹配 */ #include<bits/stdc++.h> using namespace std; const int MXN = 2e2 + 5; class Dhs { public: static const int D_MXN = 5020; static const int D_MXE = 100005; static const int D_MXQL = 20005; int n; int eCnt, head[D_MXN], nex[D_MXE], to[D_MXE]; int dui[D_MXQL], hed, tail; int fa[D_MXN], id[D_MXN], pre[D_MXN], match[D_MXN], vis[D_MXN], Tim; inline void add_edge(int u, int v) { nex[++ eCnt] = head[u]; to[eCnt] = v; head[u] = eCnt; nex[++ eCnt] = head[v]; to[eCnt] = u; head[v] = eCnt; } inline int Fi(int x) { if (fa[x] != x) fa[x] = Fi(fa[x]); return fa[x]; } inline int lca(int x, int y) { ++ Tim; while (vis[x] != Tim) { if (x) { x = Fi(x); if (vis[x] == Tim) return x; vis[x] = Tim; if (match[x] != 0) x = Fi(pre[match[x]]); else x = 0; } swap(x, y); } return x; } inline void change(int x, int y, int k) { //把奇环上的点缩成一个点，并且把原来是奇点的点变成偶点，加入队列 while (Fi(x) != k) { pre[x] = y; int z = match[x]; if (id[z] == 1) { id[z] = 0; dui[++tail] = z; } if (Fi(z) == z) fa[z] = k; if (Fi(x) == x) fa[x] = k; y = z; x = pre[y]; } } inline bool bfs(int ini) { for (int i = 1; i <= n; i++) id[i] = -1, fa[i] = i; hed = tail = 0; dui[++tail] = ini; id[ini] = 0; int u; while (hed < tail) { u = dui[++hed]; for (int i = head[u]; i; i = nex[i]) { int v = to[i]; if (id[v] == -1) { pre[v] = u; id[v] = 1; if (!match[v]) { int last, t, now = v; while (now != 0) { t = pre[now]; last = match[t]; match[t] = now; match[now] = t; now = last; } return true; } id[match[v]] = 0; dui[++tail] = match[v]; } else if (id[v] == 0 && Fi(u) != Fi(v)) { //出现奇环且不是在同一个环中 int g = lca(u, v); change(u, v, g); change(v, u, g); } } } return false; } void init(int _n) { n = _n; eCnt = Tim = 0; for (int i = 1; i <= n; ++i) { head[i] = match[i] = vis[i] = pre[i] = 0; } } int max_match() { int ans = 0; for (int i = 1; i <= n; i++) if (!match[i] && bfs(i)) ++ans; // printf("%dn", ans); // for (int i = 1; i <= n; i++) printf("%d ", match[i]); // puts(""); return ans; } } dhs; int n, m, sum_du, inde; int id[MXN][MXN], contest[MXN][2], du[MXN]; int ein[MXN][2]; int main() { int tim = read(), cas = 0; while(tim --) { n = read(), m = read(); sum_du = inde = 0; for(int i = 1; i <= n; ++i) du[i] = 0; for(int i = 1; i <= m; ++i) { ein[i][0] = read(); ein[i][1] = read(); ++ du[ein[i][0]]; ++ du[ein[i][1]]; contest[i][0] = ++ inde; contest[i][1] = ++ inde; } int flag = 0; for(int i = 1; i <= n; ++i) { id[i][0] = read(); if(id[i][0] > du[i]) flag = 1; if(flag) continue; sum_du += id[i][0]; for(int j = 1; j <= id[i][0]; ++j) { id[i][j] = ++ inde; } } printf("Case %d: ", ++ cas); if(flag || sum_du % 2 == 1) { printf("NOn"); continue; } dhs.init(inde); for(int i = 1, a, b; i <= m; ++i) { a = ein[i][0], b = ein[i][1]; dhs.add_edge(contest[i][0], contest[i][1]); for(int j = 1; j <= id[a][0]; ++j) { dhs.add_edge(id[a][j], contest[i][0]); } for(int j = 1; j <= id[b][0]; ++j) { dhs.add_edge(id[b][j], contest[i][1]); } } printf("%sn", dhs.max_match() == inde / 2?"YES":"NO"); } #ifndef ONLINE_JUDGE system("pause"); #endif return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183Tutte矩阵
叉姐模板
2020牛客多校第一场 i 题
#include <bits/stdc++.h> const int N = 50; const int M = 100; const int MOD = 1e9 + 7; int inverse(int a) { return a == 1 ? 1 : static_cast<uint64_t>(MOD - MOD / a) * inverse(MOD % a) % MOD; } template<int V> int tutte(int n, const std::vector<std::pair<int, int>> &edges, int seed) { static int mat[V][V]; memset(mat, 0, sizeof(mat)); std::mt19937 gen(seed); std::uniform_int_distribution<int> dist(1, MOD - 1); for (auto &&e : edges) { auto x = dist(gen); mat[e.first][e.second] = x; mat[e.second][e.first] = MOD - x; } int rank = 0; for (int j = 0; j < n; ++j) { int pivot = rank; while (pivot < n && !mat[pivot][j]) { pivot++; } if (pivot < n) { for (int k = 0; k < n; ++k) { std::swap(mat[rank][k], mat[pivot][k]); } const uint64_t inv = inverse(mat[rank][j]); for (int i = rank + 1; i < n; ++i) { if (mat[i][j]) { const uint64_t tmp = inv * mat[i][j] % MOD; for (int k = j; k < n; ++k) { mat[i][k] += MOD - tmp * mat[rank][k] % MOD; if (mat[i][k] >= MOD) { mat[i][k] -= MOD; } } } } rank++; } } return rank; } #ifndef NO_MAIN int deg[N]; int main() { int n, m; while (scanf("%d%d", &n, &m) == 2) { int demand = 0; for (int i = 0; i < n; ++i) { scanf("%d", deg + i); demand += deg[i]; } std::vector<std::pair<int, int>> edges; for (int i = 0, a, b; i < m; ++i) { scanf("%d%d", &a, &b); a--, b--; if (deg[a] == 2) { std::swap(a, b); } if (deg[a] == 2) { edges.emplace_back(a << 1 | 0, n + i << 1 | 0); edges.emplace_back(a << 1 | 1, n + i << 1 | 0); edges.emplace_back(b << 1 | 0, n + i << 1 | 1); edges.emplace_back(b << 1 | 1, n + i << 1 | 1); edges.emplace_back(n + i << 1 | 0, n + i << 1 | 1); demand += 2; } else if (deg[b] == 2) { edges.emplace_back(a << 1, b << 1 | 0); edges.emplace_back(a << 1, b << 1 | 1); } else { edges.emplace_back(a << 1, b << 1); } } puts(tutte<(N + M) << 1>(n + m << 1, edges, 0) == demand ? "Yes" : "No"); } } #endif
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687相关知识
一般图最大匹配：带花树入门详解
花店橱窗布置（带权二分图最大匹配）
花卉匹配大师下载
正则表达式（regex）实现模式匹配
花与婚礼：选择匹配主题和季节的婚礼花卉装饰
【图】“Rose
判断花括号是否匹配
专业ER图（实体关系图）工具
地名地址匹配算法研究
GS稳定匹配算法算法
网址: 一般图的最大匹配 https://m.huajiangbk.com/newsview1023449.html
| 上一篇: 花树无情也有情——读雷抒雁散文诗 |
下一篇: 隋炀帝萧后冠西安首露真容 揭示隋 |
