【整理】算法竞赛图论进阶学习笔记
|
|
0
|
算法
|
475

3131 字
|
30 分钟

图匹配

二分图匹配

判定

  • 静态：黑白染色。
  • 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。
    分层并查集经典例题：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 棋盘石子游戏

代码

最大匹配：匈牙利算法

bool dfs(int u,int tag){
    if(vis[u]==tag) return 0;
    vis[u]=tag;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!lnk[v]||dfs(lnk[v],tag)){
            lnk[v]=u;
            return 1;
        }
    }
    return 0;
}
//下面放进主程序
for(int i=1;i<=n;i++){
    if(dfs(i,i)) ans++;
}

最优匹配：KM 算法

本代码使用 dfs 做法，时间复杂度为 $O(n^2m)$，在洛谷上仅能获得 55 分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
const int M=5e5+5;
const int inf=19980732;
const int INF=1e9;
struct node{
    int to,nxt,w;
}e[M];
int cnt,head[N],L[N],R[N];
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
int n,m,match[N];
bool visx[N],visy[N];
bool dfs(int u){
    if(visx[u]) return 0;visx[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(visy[v]||L[u]+R[v]!=e[i].w) continue;
        visy[v]=1;
        if(!match[v]||dfs(match[v])){
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1,y,c,h;i<=m;i++){
        scanf("%lld%lld%lld",&y,&c,&h);
        add(y,c,h);
    }
    for(int u=1;u<=n;u++){
        L[u]=-inf;
        for(int i=head[u];i;i=e[i].nxt){
            L[u]=max(L[u],e[i].w);
        }
    }
    for(int u=1;u<=n;u++){
        while(1){
            for(int i=1;i<=n;i++) visx[i]=visy[i]=0;
            if(dfs(u)) break;
            int d=INF;
            for(int j=1;j<=n;j++){
                if(!visx[j]) continue;
                for(int i=head[j];i;i=e[i].nxt){
                    int v=e[i].to;
                    if(visy[v]) continue;
                    d=min(d,L[j]+R[v]-e[i].w);
                }
            }
            if(d==INF) break;
            for(int i=1;i<=n;i++){
                if(visx[i]) L[i]-=d;
                if(visy[i]) R[i]+=d;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=L[i]+R[i];
    }
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++){
        printf("%lld ",match[i]);
    }
    return 0;
}

一般图最大匹配：带花树算法

#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;
}

连通性

无向图的割点与桥

无向图的割点与桥都可通过 Tarjan 算法求得。
其核心思想是基于搜索树的，当理解有疑惑时，可以通过搜索树来理解。注意，在无向图中是只有搜索树边和返祖边，而没有横插边的。

割点与点双连通分量以及其缩点

割点有两种情况

  1. 是开始搜索的点：若存在多个儿子，则就是割点。
  2. 其他点：对于一个点 $u$, 若存在一个儿子结点 $v$，满足 $low_v \ge dfn_u$ 则 $u$ 是一个割点。

如何寻找点双连通分量？由于一个割点可能属于多个点双连通分量，我们可以维护一个栈，当第一次访问某节点时，将其入栈，当 $low_v \ge dfn_u$ 时，不断从栈中弹出节点，直至 $v$ 点被弹出，这些被弹出的点和点 $u$ 共同构成一个点双连通分量。

如何缩点？保留所有割点，并将其与所在点双连通分量连边，然后缩点所有不为割点的点。

模板：【模板】割点（割顶）
经典例题：[HNOI2012]矿场搭建

桥与边双连通分量以及其缩点

当出现 $low_v \ge dfn_u$ 时，$u,v$ 这条边形成了桥。

如何寻找边双连通分量？删除所有桥，然后剩余的每个连通块都是一个边双联通分量。我们只需要标记出桥然后 dfs 一遍全图即可。

如何缩点？把所有点双连通分量缩成一个点，再用原来的桥将其相连。

有向图的强连通分量

Kosaraju 算法

对原图进行一次 dfs（任意起点）直至遍历过所有点，然后以第一次搜索出栈时间的逆序对反图进行 dfs，对于一个点 $u$，这次搜索能到达的点和 $u$ 点都在一个强连通分量里，然后将这个点 $u$ 删去。

Tarjan 算法

维护一个栈，只有横插边或返祖边涉及的点是一个还没出栈的点时，才更新其 $low$ 值。

模板：【模板】缩点
经典例题：[HAOI2010]软件安装

2-SAT

参考：Plozia-图论专题-学习笔记：2 – SAT 问题

2-sat，即每个变量可能状态只有两种（0/1），然后给出很多变量间的关系，求一组可能的解或报告无解。为了解决这个问题，我们通常是把每个变量拆为两个点，然后把变量关系转化为有向边，最后跑强连通分量。下记点 $x$ 为 $0$ 对应点为 $x_0$，反之为 $x_1$。记 $\bar{0}=1,\bar{1}=0$

2-sat 的所有情况都可以化归为以下三种情况：

  • 若 $A=p$，则 $B=q$
    • 连线方案：$A_p \to B_q, B_\bar{q} \to A_\bar{p}$
  • $A=p$ 或 $B=q$（两者至少有一者成立，而不是只有一者 i.e. inclusive or）
    • 连线方案：$A_\bar{p} \to B_q, B_\bar{q} \to A_p$
  • $A$ 为 $p$
    • 连线方案：$A_{\bar{p}} \to A_p$

连线完成后，我们跑一遍 Tarjan，然后对于两点 $x_0$ 和 $x_1$，我们取其中拓扑序较大的点，即 $col_u$ 较小的点。(注意在 tarjan 中，越早被染色的点拓扑序越大)

模板：【模板】2-SAT

代码

割点（Tarjan 算法）

int n,m,dfn[N],low[N],tot,cut[N];
long long ans,siz,ans2;
void tarjan(int u,int ori){
    int son=0;
    dfn[u]=++tot;
    low[u]=tot;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            son++;
            tarjan(v,ori);low[u]=min(low[u],low[v]);
            if(u!=ori&&low[v]>=dfn[u]) cut[u]=1;
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(u==ori&&son>=2) cut[u]=1;
}

缩点（Tarjan 算法）

int dfn[N],low[N],insta[N],tot,colcnt,col[N];
stack<int> st;
void tarjan(int u){
    dfn[u]=++tot;
    low[u]=tot;
    st.push(u);insta[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(insta[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        colcnt++;
        while(st.top()!=u){
            col[st.top()]=colcnt;
            insta[st.top()]=0;
            st.pop();
        }
        col[st.top()]=colcnt;
        insta[st.top()]=0;
        st.pop();
    }
}

网络流

最大流

SAP 算法

给每个点一个距离标号 $D_i$，则距离标号为 $x$ 的点只能流向距离标号为 $x+1$ 的点。初始时所有点标号均为 $0$，当发现当前点无法走出去，就提高一级距离标号，直到产生断层（有一个距离标号没有任何点）或者有点被提高了 $n$ 次（不可能有点会到 $n+1$ 层），则停止继续寻找可行流。

Dinic 算法

先用一遍 bfs 给图进行分层，然后在 dfs 寻找可行流的过程中，只流向下一层的点。
当 bfs 无法到达汇点时，停止寻找。

例题:
[SCOI2007] 蜥蜴
[网络流24题]圆桌问题

最小割

最大流=最小割

例题：
[网络流24题]方格取数问题
[JSOI2016] 反质数序列

最小费用最大流

将 dinic 算法中的 bfs 改成以费用为边权的 spfa，然后 dfs 中的条件改为在最小路上($dis_v=dis_u+e_i.c$，其中 $c$ 是费用)即可。

例题：
[网络流24题]运输问题
[网络流24题]航空路线问题

有上下界的网络流

  • Step 1: 建新的源点 $S’$ 和汇点 $T’$。
  • Step 2: 若点 $u$ 到点 $v$ 的流量要求为 $[a,b]$，则点 $S’$ 向点 $v$ 连流量为 $a$ 的边，点 $u$ 向点 $T’$ 连流量为 $a$ 的边，点 $u$ 向点 $v$ 连流量为 $b-a$ 的边（相当于将新增的源点和汇点作为中转点，以此保证所有下限都能满足）。
  • Step 3: 原来的汇点 $T$ 向源点 $S$ 连一条流量无限的边。
  • Step 4: 用新源点 $S’$ 和汇点 $T’$ 跑最大流。若未满流，则条件无法达成，退出。否则进行 Step 5。
  • Step 5：删除 Step 2 中与 $S’$ 和 $T’$ 有关的边，以及 Step 3 中新连的边。然后在当前的残量网络中以原来的源点 $S$ 和汇点 $T$ 再跑一次最大流。
  • Step 6：两次最大流流量的和即为最终的最大流。

例题：
Budget

代码

网络最大流（SAP 算法）

ll ans;
bool vis[N];
ll dfs(int u,ll flow){
    if(vis[u]) return 0;
    if(u==t) return flow;
    ll sum=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        ll w=e[i].w;
        if(w&&d[v]+1==d[u]){
            int tmp=dfs(v,min(flow-sum,w));
            e[i].w-=tmp;
            e[i^1].w+=tmp;
            sum+=tmp;if(sum==flow) return sum;
        }
    }
    if(!sum) vis[u]=1;
    if(d[s]>=n) return sum;
    cntd[d[u]]--;
    if(!cntd[d[u]]) d[s]=n;
    d[u]++;cntd[d[u]]++;
    return sum;
}
//下面放进主程序
for(int i=1,u,v,w;i<=m;i++){
    scanf(,&u,&v,&w);
    add(u,v,w);add(v,u,0);
}
cntd[0]=n;
while(d[s]<n){
    for(int i=1;i<=n;i++) vis[i]=0;
    ans+=dfs(s,MAX);
}
//记得建图的cnt改为1

网络最大流（Dinic 算法）

ll ans;
int dep[N];
bool bfs(){
    for(int i=1;i<=n;i++) dep[i]=0;
    queue<int> q;q.push(s);dep[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(e[i].w&&(!dep[v])){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if(dep[t]) return true;
    return false;
}
ll dfs(int u,ll flow){
    if(u==t) return flow;
    ll sum=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].w&&dep[v]==dep[u]+1){
            int tmp=dfs(v,min(flow-sum,e[i].w));
            e[i].w-=tmp;e[i^1].w+=tmp;
            sum+=tmp;if(sum==flow) return sum;
        }
    }
    if(!sum) dep[u]=0;
    return  sum;
}
//下面放进主程序
for(int i=1,u,v,w;i<=m;i++){
    scanf(,&u,&v,&w);
    add(u,v,w);add(v,u,0);
}
while(bfs()){
    ans+=dfs(s,1e18);
}
//记得建图的cnt改为1

最小费用最大流（MCMF）

int ans1,ans2,dis[N];
int n,m,s,t;
bool vis[N];
bool spfa(){
    for(int i=1;i<=n;i++) dis[i]=inf;
    for(int i=1;i<=n;i++) vis[i]=0;
    queue<int> q;q.push(s);dis[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(!e[i].w) continue;
            if(dis[v]>dis[u]+e[i].c){
                dis[v]=dis[u]+e[i].c;
                if(!vis[v]){vis[v]=1;q.push(v);}
            }
        }
    }
    if(dis[t]==inf) return 0;
    return 1;
}
int dfs(int u,int flow){
    vis[u]=1;
    if(u==t) return flow;
    int sum=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!vis[v]&&dis[v]==dis[u]+e[i].c&&e[i].w){
            int tmp=dfs(v,min(flow-sum,e[i].w));
            e[i].w-=tmp;e[i^1].w+=tmp;
            sum+=tmp;ans2+=tmp*e[i].c;
            if(sum==flow) return sum;   
        }
    }
    return sum;
}
void MCMF(){
    while(spfa()){
        vis[t]=1;
        while(vis[t]){
            for(int i=1;i<=n;i++) vis[i]=0;
            ans1+=dfs(s,inf);
        }
    }
}
//下面放进主程序
for(int i=1,u,v,w,c;i<=m;i++){
    scanf(,&u,&v,&w,&c);
    add(u,v,w,c);add(v,u,0,-c);
}
MCMF();
//记得建图的cnt改为1
本文作者：water_tomato
ACMtarjan二分图割点图匹配强连通分量最大流最小割算法缩点网络流连通性
暂无评论

发送评论 编辑评论

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