ZR 集训 Day27 – 匹配与网络流

ooliver 发布于 2026-08-12 376 次阅读 OI

AI 摘要

匹配、点覆盖、独立集、路径覆盖……看似毫不相干，却全被“最大匹配=最小点覆盖”一箭穿心。更妙的是，平面图最小割竟能化作对偶图最短路。拆点图、Hall定理、KM算法——这些利器如何把“狼抓兔子”变成最短路模板？看完笔记，你会惊呼：原来都藏着同一把钥匙。

一些笔记

一些关系

二分图匹配大小 = 最小点覆盖大小 = $|V|$ - 二分图最大独立集。

DAG 最小路径覆盖 = $|V|$ - 拆点图注最大匹配 = 偏序集最长反链（即在 DAG 上选出最大的两两不可到达的点集）。

什么是拆点图？

对于 DAG 中每一条边 $u \rightarrow v$，我们在新图中连无向边：$(u_r,v_l)$，则形成了一个二分图。这个二分图即原 DAG 的拆点图。

Hall 定理

邻集定义：

$$
N(S) = { v \in Y \mid \exists u \in S,\ (u,v) \in E }
$$

$N(S)$：集合 $S$ 的邻集，即 $S$ 中所有顶点能一步到达的邻居的集合。
$S$：左侧顶点集合 $X$ 的任意一个子集。
$Y$：二分图右侧的顶点集合。
$E$：二分图中所有边的集合。

霍尔定理：

$$
\forall S \subseteq X,\quad |S| \le |N(S)|
$$

$|S|$：集合 $S$ 中顶点的个数。
$|N(S)|$：集合 $N(S)$ 中顶点的个数。

König-Hall 公式（最大匹配数）：

$$
\nu(G) = |X| - \max_{S \subseteq X} \big( |S| - |N(S)| \big)
$$

$\nu(G)$：最大匹配大小。
$|X|$：左侧顶点总数。
$\max_{S \subseteq X}$：在所有子集 $S$ 中取最大值。

缺陷形式：

$$
\delta = \max_{S \subseteq X} \big( |S| - |N(S)| \big)
$$

$$
\nu(G) = |X| - \delta
$$

$\delta$：缺陷值，必须放弃的最少顶点数。

网络流相关

最大流 = 最小割

平面图最小割 = 对偶图注最短路

什么是对偶图？

对偶图是与平面图相伴的一种图。在图论中，对偶图是通过将平面图的面转换为顶点，并将面之间的公共边转换为对偶图中的边来构造的。

对偶图的构造方法

  1. 选择顶点：在给定平面图的每个面中任选一个点作为对偶图的顶点。
  2. 连接边：对于平面图中两个面共有的边，在对偶图中连接这两个面的顶点，并且连线穿过这条公共边。
  3. 处理割边：如果平面图中的某条边是某个面的割边，则在对偶图中以该面的顶点作环，并让它与这条边相交。

对偶图的性质

  • 顶点数：对偶图的顶点数等于原平面图的面数。
  • 边数：对偶图的边数等于原平面图的边数。
  • 面数：对偶图的面数等于原平面图的顶点数。
  • 度数关系：对偶图中顶点的度数等于原平面图中对应面的度数。

P6577 【模板】二分图最大权完美匹配

模板题。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const ll inf=2e18;

int n,m;
int match[N],pre[N];
bool vis[N];
ll la[N],lb[N],d[N],w[N][N];

void bfs(int u){
    fill(d+1,d+1+n,inf);
    fill(vis+1,vis+1+n,0);
    int x,y=0,yy=0;
    match[y]=u;
    while(match[y]){
        x=match[y];
        ll delta=inf;
        vis[y]=1;
        for(int i=1;i<=n;i++){
            if(vis[i]) continue;
            if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]<delta) delta=d[i],yy=i;
        }
        for(int i=0;i<=n;i++){
            if(vis[i]) la[match[i]]-=delta,lb[i]+=delta;
            else d[i]-=delta;
        }
        y=yy;
    }
    while(y) match[y]=match[pre[y]],y=pre[y];
}

ll km(){
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) la[i]=max(la[i],ll(w[i][j]));
    for(int i=1;i<=n;i++) bfs(i);
    ll res=0;
    for(int i=1;i<=n;i++) res+=w[match[i]][i];
    return res;
}

signed main(){
    cin>>n>>m;
    fill(&w[1][1],&w[n+1][n+1],-inf);
    fill(la+1,la+1+n,-inf);
    for(int i=1,u,v,wis;i<=m;i++){
        cin>>u>>v>>wis;
        w[u][v]=max(w[u][v],ll(wis));
    }
    cout<<km()<<"\n";
    for(int i=1;i<=n;i++) cout<<match[i]<<" ";
    return 0;
}

P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

考虑对 $i>j$ 且异色的两点连有向边，原题转换成求 DAG 最小路径覆盖问题。所以将原图进行拆点，变成一个二分图，左侧每个点都与右侧异色且长度大于自己的点连边。而我们需要对这个二分图求最大匹配，再套一个霍尔定理（上面有解释）可知：

$$
\begin{aligned}
Ans&=n-\nu(G) \\
&=n- (n - \max_{S \subseteq X} \big( |S| - |N(S)| \big) ) \\
&=\max_{S \subseteq X} \big( |S| - |N(S)| \big) )
\end{aligned}
$$

其中 $X$ 就是左侧点集。

不难发现对于这个 $\max$，两个颜色是独立的，所以可以看作是两个颜色的 $\max$ 相加。因为 $N(S)$ 一定是当前前缀异色积木的数量，否则枚举到当前前缀就没有意义了，那想要 $S$ 最大，即把所有同色点都选上，这个可以前缀和一下。对于一个询问就相当于求区间 $\max$，可以用 ST 表解决。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int n,q;
int sum[N];

struct ST{
    int st[N][20];
    void init(){
        for(int j=1;j<19;j++)
            for(int i=0;i<=n-(1<<j)+1;i++)
                st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
    int get(int l,int r){
        int k=log2(r-l+1);
        return max(st[l][k],st[r-(1<<k)+1][k]);
    }
}s1,s2;

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        sum[i]=sum[i-1]+((c=='P')?1:-1);
        s1.st[i][0]=sum[i],s2.st[i][0]=-sum[i];
    }
    s1.init(),s2.init();
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<s1.get(l-1,r)+s2.get(l-1,r)<<"\n";
    }
    return 0;
}

P2764 最小路径覆盖问题

上面有笔记，这里解释一下。

每次合并两条路径，答案就会减 $1$，最开始的路径数量显然是 $|V|$，当我们建立拆点图，找到一个匹配 $out_u,in_v$，说明以 $u$ 结尾的链与以 $v$ 开头的链进行了合并操作，答案就减 $1$，所以我们对拆点图跑最大二分图匹配即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=305;
int n,m,ans;
int match[N],to[N],vis[N];
vector<int> g[N];

bool dfs(int u){
    for(int v:g[u]){
        if(vis[v]) continue;
        vis[v]=1;
        if(!match[v]||dfs(match[v])){
            match[v]=u,to[u]=v;
            return 1;
        }
    }
    return 0;
}

signed main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        fill(vis+1,vis+1+n,0);
        vis[i]=1;
        if(dfs(i)) ans++;
    }
    for(int i=1;i<=n;i++){
        if(!match[i]){
            int x=i;
            while(x!=0){
                cout<<x<<" ";
                x=to[x];
            }
            cout<<"\n";
        }
    }
    cout<<n-ans;
    return 0;
}

P3967 [TJOI2014] 匹配

二分图最大权完美匹配。

看到 $n$ 的范围很小，想到第一问现跑一遍 $KM$，之后枚举一组解内的所有匹配边，如果删边之后答案变小了，说明这个边是必须要有的，就输出。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
const int N=85;
const int inf=1e9;

int n,m,ans;
int match[N],pre[N];
bool vis[N];
int la[N],lb[N],d[N],w[N][N];
vector<pair<int,int>> pr;

void bfs(int u){
    fill(d+1,d+1+n,inf);
    fill(vis+1,vis+1+n,0);
    int x,y=0,yy=0;
    match[y]=u;
    while(match[y]){
        x=match[y];
        int delta=inf;
        vis[y]=1;
        for(int i=1;i<=n;i++){
            if(vis[i]) continue;
            if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]<delta) delta=d[i],yy=i;
        }
        for(int i=0;i<=n;i++){
            if(vis[i]) la[match[i]]-=delta,lb[i]+=delta;
            else d[i]-=delta;
        }
        y=yy;
    }
    while(y) match[y]=match[pre[y]],y=pre[y];
}

int km(){
    for(int i=1;i<=n;i++) la[i]=-inf,match[i]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) la[i]=max(la[i],w[i][j]);
    for(int i=1;i<=n;i++) bfs(i);
    int res=0;
    for(int i=1;i<=n;i++) res+=w[match[i]][i];
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>w[i][j];
    cout<<(ans=km())<<"\n";
    for(int i=1;i<=n;i++) pr.push_back({match[i],i});
    sort(pr.begin(),pr.end());
    for(auto[u,v]:pr){
        int wis=w[u][v];
        w[u][v]=-inf;
        if(km()<ans) cout<<u<<" "<<v<<"\n";
        w[u][v]=wis;
    }
    return 0;
}

P2053 [SCOI2007] 修车

考虑把每个师傅修不同车的状态设置为左部点集，把所有车作为右部点集，跑二分图最大权匹配，但是因为修车可以同时进行，这个边权不好算。所以我们考虑设置状态时按照每个师傅修这辆车时是倒数第 $k$ 个，这样对答案的贡献就是 $k*t_{i,j}$。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
const int N=550;
const int inf=1e9;

int n,m,ans;
int match[N],pre[N];
bool vis[N];
int la[N],lb[N],d[N],w[N][N],t[N][N];
vector<pair<int,int>> pr;

void bfs(int u){
    fill(d+1,d+1+n,inf);
    fill(vis+1,vis+1+n,0);
    int x,y=0,yy=0;
    match[y]=u;
    while(match[y]){
        x=match[y];
        int delta=inf;
        vis[y]=1;
        for(int i=1;i<=n;i++){
            if(vis[i]) continue;
            if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]<delta) delta=d[i],yy=i;
        }
        for(int i=0;i<=n;i++){
            if(vis[i]) la[match[i]]-=delta,lb[i]+=delta;
            else d[i]-=delta;
        }
        y=yy;
    }
    while(y) match[y]=match[pre[y]],y=pre[y];
}

int km(){
    for(int i=1;i<=n;i++) la[i]=-inf,match[i]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) la[i]=max(la[i],w[i][j]);
    for(int i=1;i<=n;i++) bfs(i);
    int res=0;
    for(int i=1;i<=n;i++) res+=w[match[i]][i];
    return res;
}

signed main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        cin>>t[i][j];
        for(int k=1;k<=n;k++) w[i][(j-1)*n+k]=-k*t[i][j];
    }
    n=m*n;
    cout<<fixed<<setprecision(2)<<km()*(-1.0)/(n/m);
    return 0;
}

P4001 [ICPC 2006 Beijing R] 狼抓兔子

根据上面的笔记，我们知道平面图的最小割等于其对偶图的最长路。

我们把起点和终点连一条虚边，这样外面的大面就被分成了两个面，本来外面只有一个点，现在变成了两个点。其目的是将平面图最小割在对偶图上的体现从一个环断成了一条链，就可以利用这两个点跑最短路。

对偶图的建图就是给相邻两个面建边，边权就是连接这两个面的边的边权。

建图后跑最短路即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;

struct graph{
    int n;
    vector<pair<int,int>> g[N];
    void init(int x){
        n=x;
        for(int i=1;i<=n;i++) g[i].clear();
    }
    void add(int u,int v,int w){
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    int dij(int s,int t){
        vector<int> dis(n+1,1e18),vis(n+1,0);
        priority_queue<pair<int,int>> q;
        q.push({0,s});
        dis[s]=0;
        while(q.size()){
            auto[d,u]=q.top();
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto[v,w]:g[u]){
                if(!vis[v]&&dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    q.push({-dis[v],v});
                }
            }
        }
        return dis[t];
    }
}g;

int n,m,w,s,t;

int id(int x,int y,int k){
    return ((x-1)*(m-1)+y+k*(n-1)*(m-1));
}

signed main(){
    cin>>n>>m;
    s=2*(n-1)*(m-1)+1,t=2*(n-1)*(m-1)+2;
    g.init(2*(n-1)*(m-1)+2);
    for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++){
        cin>>w;
        if(i==1) g.add(id(i,j,1),t,w);
        else if(i==n) g.add(s,id(i-1,j,0),w);
        else g.add(id(i,j,1),id(i-1,j,0),w);
    }
    for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++){
        cin>>w;
        if(j==1) g.add(s,id(i,j,0),w);
        else if(j==m) g.add(id(i,j-1,1),t,w);
        else g.add(id(i,j-1,1),id(i,j,0),w);
    }
    for(int i=1;i<=n-1;i++) for(int j=1;j<=m-1;j++){
        cin>>w;
        g.add(id(i,j,0),id(i,j,1),w);
    }
    cout<<g.dij(s,t);
    return 0;
}