带花树
Neutralized
·
·
个人记录
2022.12.15。
解决一般图最大匹配问题。
一般图存在奇环，而奇环可以直接卡掉匈牙利算法，所以需要一些改进。
对于一个奇环，点数为 2k+1，那么它的内部最多有 k 组匹配，并且会有一个点向外匹配，如果将内部匹配忽略，就可以直接看成一个点，因为不管是哪个点向外匹配都可以调整内部匹配使得产生总共 k+1 组匹配。所以可以直接 把奇环缩成一个点 来处理。
使用并查集维护奇环的根（最高点），如果将 match 和 pre 看作边（匹配边是 match，连接两组匹配的边是 pre），就会获得一棵树。新出现一个奇环时，求出 u,v 的 \text{LCA}（注意这部分可以暴力求，因为每次求完之后就会缩点，路径上的点只会被访问一次，总复杂度 O(n)），然后分别进行 \textbf{Blossom(u,v,lca)} 和 \textbf{Blossom(v,u,lca)} 操作。
```cpp
inline int LCA(int a,int b){
static int Dfn=0; ++Dfn,a=Find(a),b=Find(b);
while(dfn[a]!=Dfn){ dfn[a]=Dfn,a=Find(pre[mat[a]]); if(b) swap(a,b); } return a;
}
```
$\textbf{Blossom}$：
```cpp
inline void Blossom(int a,int b,int lca){
while(Find(a)!=lca){
pre[a]=b,b=mat[a]; if(col[b]==2) col[b]=1,q[++r]=b;
if(Find(a)==a) Fa[a]=lca; if(Find(b)==b) Fa[b]=lca; a=pre[mat[a]];
}
}
```
$\textbf{Match}$（$\text{BFS}$）：
```cpp
inline bool Match(int S){
auto Rec = [](int u,int lst=0){ while(u) lst=mat[pre[u]],mat[u]=pre[u],mat[pre[u]]=u,u=lst; };
for(int i=1;i<=n;++i) col[i]=pre[i]=0,Fa[i]=i;
q[l=r=col[S]=1]=S; while(l<=r){
int u=q[l++]; gfore(u)
if(Find(u)!=Find(v=e[i].to)&&col[v]!=2){
if(!col[v]){
col[v]=2,pre[v]=u; if(!mat[v]) return Rec(v),1;
col[mat[v]]=1,q[++r]=mat[v];
} else{ int lca = LCA(u,v); Blossom(u,v,lca),Blossom(v,u,lca); }
}
} return 0;
}
```
必须 **注意黑白点往前跳的方式**，`Rec()` 中是白点开始不停跳白点，所以是 `mat[pre[u]]`，而 `LCA()` 和 `Blossom()` 都是黑点开始的所以用 `pre[mat[u]]`。
感觉复杂度是 $O(n^3)$ 左右（？，~~但是从速度上看起来很网络流啊。~~
***
- ZOJ3316
Qry：有一个 $19 \times 19$ 的棋盘，$n$ 个棋子，两人轮流取，每次取的棋子和上一个人取的棋子的曼哈顿距离 $\le L$，均以最优策略进行，判断后手能否获胜。$n \le 361$。
Sol：直接 $n^2$ 连边，获得一张一般图，显然当存在完美匹配的时候后手必胜，只要顺着匹配选就行了，反之先手必胜。直接做就行了。
- HDU3551
Qry：给出一张无向图，可能有重边，无自环，给出一个序列 $\{a_n\}$，求任意一张生成子图满足点 $i$ 的度数是 $a_i$。$n \le 50,m \le 100$。
Sol：对每条边拆成两个点，分别向两个端点拆成的度数点连边，求出完美匹配后就是方案。
放个完整代码：
```cpp
const int N = 3003;
int n,m,tot,a[53],pre[N],col[N],mat[N],q[N],l,r,Fa[N],dfn[N];
vector<int> e[N],nd[53]; vector<pair<int,int> > E;
inline void add(int u,int v){ e[u].emplace_back(v); }
inline void Add(int u,int v){ add(u,v),add(v,u); }
inline int Find(int x){ return x==Fa[x]?x:Fa[x]=Find(Fa[x]); }
inline int LCA(int a,int b){
static int Dfn = 0; ++Dfn,a=Find(a),b=Find(b);
while(dfn[a]^Dfn) dfn[a]=Dfn,a=Find(pre[mat[a]]),b&&(a^=b^=a^=b); return a;
}
inline void Blossom(int a,int b,int lca){
while(Find(a)^lca){
pre[a]=b,b=mat[a]; if(col[b]==2) col[b]=1,q[++r]=b;
if(Find(a)==a) Fa[a]=lca; if(Find(b)==b) Fa[b]=lca; a=pre[mat[a]];
}
}
inline bool Match(int x){
auto R = [](int u,int lst=0){ while(u) lst=mat[pre[u]],mat[u]=pre[u],mat[pre[u]]=u,u=lst; };
for(int i=1;i<=tot;++i) col[i]=pre[i]=0,Fa[i]=i;
q[l=r=col[x]=1]=x; while(l<=r){
int u=q[l++]; for(int v:e[u])
if(Find(u)!=Find(v)&&col[v]!=2){
if(!col[v]){
col[v]=2,pre[v]=u; if(!mat[v]) return R(v),1;
col[mat[v]]=1,q[++r]=mat[v];
} else{ int lca = LCA(u,v); Blossom(u,v,lca),Blossom(v,u,lca); }
}
} return 0;
}
main(){
int T; rd(T); for(int R=1;R<=T;++R){
rd(n),rd(m),tot=m<<1,E.clear(); int res=0;
for(int i=1;i<=n;++i) nd[i].clear();
for(int i=1,u,v;i<=m;++i) rd(u),rd(v),E.emplace_back(u,v);
for(int i=1;i<=n;++i){ rd(a[i]); for(int j=1;j<=a[i];++j) nd[i].emplace_back(++tot); }
for(int i=1;i<=tot;++i) e[i].clear(),mat[i]=0;
for(int i=0;i<m;++i){
Add((i<<1)+1,(i<<1)+2);
int u=E[i].first,v=E[i].second;
for(int x:nd[u]) Add((i<<1)+1,x);
for(int x:nd[v]) Add((i<<1)+2,x);
}
for(int i=1;i<=tot;++i) if(!mat[i]&&Match(i)) ++res;
printf("Case %d: ",R),puts((res<<1)>=tot?"YES":"NO");
}
}
```
- HDU3446（没写）
Qry：给出一张 $n \times m$ 的棋盘，有一些位置 `#` 不能走，其它的 `.` 可以走，有一个王会被放在给定的地方 `K`，每一步可以走的范围如下图：
走过的格子不能再走，现在 Aloce 和 Bib （？）轮流按最优策略操作，不能移动的人就输了，问谁会获得胜利。$n,m \le 15$。
Sol：直接连边跑最大匹配，如果 `K` 一定在最大匹配里则先手必胜。
Upd on 2023.3.30：这个是一般图博弈的结论。