图匹配学习笔记

这两天零零散散地对图匹配算是进行了一个较为系统的学习,写个简单的学习笔记,既是记录,也是一边写一边帮助回忆巩固。

二分图匹配

判定

  • 静态:黑白染色。
  • 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图。
    分层并查集经典例题:P2024 [NOI2001] 食物链

最大匹配:匈牙利算法

模版:P3386 【模板】二分图最大匹配
匈牙利算法本质就是不断往前搜寻,寻找增广路的算法,代码实现上只需要注意 vis 数组的存在,防止搜索永远无法停止,其他都是容易码的。
注意时间复杂度 $O(nm)$。

Konig 定理

二分图中最大匹配数等于最小点覆盖数,即最少的能够覆盖所有边的点数。
这个思想在本题中有所运用:NC236754 炸弹

最优匹配:KM 算法

模版:P6577 【模板】二分图最大权完美匹配
KM 算法要求二分图必须为完美匹配。为满足这一点,我们可能会在本来没有边的点之间连接权值为 0 的边。
这个算法的思路是:给所有点的一个权值,左边的点初始权值为所有边的最大的值,右边的点初始权值为 0。
在二分图匹配中,仅有 $L_i+R_j=w_{i,j}$ 的边会被考虑。如果匹配不成功,对于所有在本次寻找增广路中找过的点,我们在所有其对应的右边点中寻找一个损失最小的点,即 $d=L_i+R_j-w_{i,j}$ 最小的点。然后对于所有在本次寻找增广路中的找过的点,若其是左边点,权值减 $d$,若其是右边点,权值加 $d$,这样我们就扩展了点集。
一个点一个点地寻找匹配,周而复始,可以得到答案。
dfs 做法,时间复杂度为 $O(n^2m)$。
bfs 做法,时间复杂度为 $O(n^3)$,不过我并没有去学 bfs 做法 qwq。

Hall 定理

充要条件:对于一个二分图,如果对于左边任意子集 $S$,其对应边连接了一个右边的点集 $T$,均有 $|S|\le |T|$,则这个二分图有完美匹配。
相关题目:CF981F Round Marriage

稳定婚姻系统

不存在夫妻 $u,v$ 和 $a,b$,$u$ 对 $b$ 的好感度超过 $u$ 对 $v$,且 $b$ 对 $u$ 的好感度超过 $b$ 对 $a$。

寻找方法:对于所有左边的人,第一轮先依次尝试向右边好感度最高的人表白。对于右边的人,如果当前对她表白的人的好感度超过了她原先匹配的人的好感度,则抛弃原先的人,选择现在的人。
从第二轮开始,所有没有伴侣的左边的人会表白没有拒绝他的人中的好感度最高的那个右边的人。
以此类推,直至所有人都有伴侣。

一般图匹配

带花树算法

模版:P6113 【模板】一般图最大匹配
难度较高。每次从一个没有匹配的点开始对图重新染色,用 bfs 寻找增广路,期间如果:
1. 遇到不同色,即偶环,跳过。
2. 遇到同色,即奇环,进行缩点,并把环中所有点都纳入队列中。
3. 遇到未染色的未匹配的点,即找到增广路,交替变换匹配关系即可。
4. 遇到未染色的匹配的点:将其和与其匹配的点都染色,然后将与其匹配的点加入队列。

一道例题:NC236786 棋盘石子游戏

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=5e5+5;
struct node{
    int to,nxt;
}e[M];
int last[N],match[N],col[N],head[N],cnt;
int fa[N],ans,tmp,vis[N];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m;
int find(int u){
    return u==fa[u]?u:fa[u]=find(fa[u]);
}
queue<int> q;
int lca(int u,int v){
    tmp++;
    while(1){
        if(u!=0){
            u=find(u);
            if(vis[u]==tmp) return u;
            vis[u]=tmp;
            u=last[match[u]];
            //if(match[u]) u=last[match[u]];
            //else u=0;
        }
        swap(u,v);
    }
}
void flower(int u,int L){
    while(u!=L){
        int v=match[u],z=last[v];
        if(find(z)!=L) last[z]=v;
        if(col[v]==2){col[v]=1;q.push(v);}
        if(col[z]==2){col[z]=2;q.push(z);}
        fa[find(u)]=find(v);
        fa[find(v)]=find(z);
        u=z;
    }
}
int solve(int s){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++){
        col[i]=last[i]=0;fa[i]=i;
    }//1:black;2:white
    q.push(s);col[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(match[u]==v) continue;
            if(find(u)==find(v)) continue;
            if(col[v]==2) continue;
            if(col[v]==1){
                int L=lca(u,v);
                if(find(u)!=L) last[u]=v;
                if(find(v)!=L) last[v]=u;
                flower(u,L);flower(v,L);
            }
            else if(!match[v]){
                last[v]=u;
                for(int x=v;x!=0;){
                    int y=last[x];
                    int z=match[y];
                    match[x]=y;match[y]=x;
                    x=z;
                }
                return 1;
            }
            else{
                last[v]=u;
                col[match[v]]=1;
                col[v]=2;
                q.push(match[v]);
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!match[i]) ans+=solve(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) printf("%d ",match[i]);
    return 0;
}
本文作者:water_tomato

评论

    发送评论 编辑评论

    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇