https://wiki.cvbbacm.com/ 2026-04-30T02:14:52+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-07-15T11:45:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:alchemist:maxdumbledore:graph:blossom_algorithm&rev=1594784737&do=diff 带花树算法 带花树算法是为了解决一般图的匹配问题的，注意这种问题是网络流构图无法可解的。 效率为$O(|V|^2|E|)$，实际表现会好得多。 下面为牛客2020多校一的I题代码，精彩的构图+带花树。 #include <bits/stdc++.h> using namespace std; const int maxn = 500; struct struct_edge { int v; struct_edge *n; }; typedef struct_edge *edge; struct_edge pool[maxn * maxn * 2]; edge top = pool, adj[maxn]; int V, match[maxn], qh, qt, q[maxn], father[maxn], base[maxn]; bool inq[maxn], inb[maxn], ed[maxn][maxn]; void addEdge(int u, int v) { --u, --v; if (!ed[u][v]) { e…