ZR 集训 Day27 - 匹配与网络流

2026年8月12日 ooliver OI

一些笔记

一些关系

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

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

什么是拆点图？

对于 DAG 中每一条边 $u \to v$ ，我们在新图中连无向边： $(u_{r}, v_{l})$ ，则形成了一个二分图。这个二分图即原 DAG 的拆点图。

Hall 定理

邻集定义：

$N (S) = v \in Y ∣ \exists u \in S, (u, v) \in E$

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

霍尔定理：

$\forall S \subseteq X, | S | [PARSE ERROR: Undefined("Command(\"le\")")] | N (S) |$

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

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

$ν (G) = | X | - \max_{S \subseteq X} [PARSE ERROR: Undefined("Command(\"big\")")] (| S | - | N (S) | [PARSE ERROR: Undefined("Command(\"big\")")])$

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

缺陷形式：

$δ = \max_{S \subseteq X} [PARSE ERROR: Undefined("Command(\"big\")")] (| S | - | N (S) | [PARSE ERROR: Undefined("Command(\"big\")")])$

$ν (G) = | X | - δ$

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

网络流相关

最大流 = 最小割

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

什么是对偶图？

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

对偶图的构造方法

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

对偶图的性质

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

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

模板题。

代码：

C++

#include
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;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]>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>u>>v>>wis;
        w[u][v]=max(w[u][v],ll(wis));
    }
    cout

`#include
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;in;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;in;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;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],ll(w[i][j]));
    for(int i=1;in;i++) bfs(i);
    ll res=0;
    for(int i=1;in;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;im;i++){
        cin>>u>>v>>wis;
        w[u][v]=max(w[u][v],ll(wis));
    }
    coutkm()"\n";
    for(int i=1;in;i++) coutmatch[i]" ";
    return 0;
}`

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

考虑对 $i [PARSE ERROR: Ampersand] g t; 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
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>n>>q;
    for(int i=1;i>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

`#include
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;j19;j++)
            for(int i=0;in-(1j)+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-(1k)+1][k]);
    }
}s1,s2;

signed main(){
    cin>>n>>q;
    for(int i=1;in;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;
        couts1.get(l-1,r)+s2.get(l-1,r)"\n";
    }
    return 0;
}`

P2764 最小路径覆盖问题

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

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

代码：

C++

#include
using namespace std;

const int N=305;
int n,m,ans;
int match[N],to[N],vis[N];
vector 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>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i

`#include
using namespace std;

const int N=305;
int n,m,ans;
int match[N],to[N],vis[N];
vectorint> 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;im;i++){
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;in;i++){
        fill(vis+1,vis+1+n,0);
        vis[i]=1;
        if(dfs(i)) ans++;
    }
    for(int i=1;in;i++){
        if(!match[i]){
            int x=i;
            while(x!=0){
                coutx" ";
                x=to[x];
            }
            cout"\n";
        }
    }
    coutn-ans;
    return 0;
}`

P3967 [TJOI2014] 匹配

二分图最大权完美匹配。

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

代码：

C++

#include
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> 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;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]>n;
    for(int i=1;i>w[i][j];
    cout

`#include
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];
vectorpairint,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;in;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;in;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;in;i++) la[i]=-inf,match[i]=0;
    for(int i=1;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],w[i][j]);
    for(int i=1;in;i++) bfs(i);
    int res=0;
    for(int i=1;in;i++) res+=w[match[i]][i];
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;in;i++) for(int j=1;jn;j++) cin>>w[i][j];
    cout(ans=km())"\n";
    for(int i=1;in;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) coutu" "v"\n";
        w[u][v]=wis;
    }
    return 0;
}`

P2053 [SCOI2007] 修车

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

代码：

C++

#include
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> 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;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y;
            if(d[i]>m>>n;
    for(int i=1;i>t[i][j];
        for(int k=1;k

`#include
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];
vectorpairint,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;in;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;in;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;in;i++) la[i]=-inf,match[i]=0;
    for(int i=1;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],w[i][j]);
    for(int i=1;in;i++) bfs(i);
    int res=0;
    for(int i=1;in;i++) res+=w[match[i]][i];
    return res;
}

signed main(){
    cin>>m>>n;
    for(int i=1;in;i++) for(int j=1;jm;j++){
        cin>>t[i][j];
        for(int k=1;kn;k++) w[i][(j-1)*n+k]=-k*t[i][j];
    }
    n=m*n;
    coutfixedsetprecision(2)km()*(-1.0)/(n/m);
    return 0;
}`

P4001 [ICPC 2006 Beijing R] 狼抓兔子

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

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

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

建图后跑最短路即可。

代码：

C++

#include
using namespace std;
#define int long long
const int N=2e6+5;

struct graph{
    int n;
    vector> g[N];
    void init(int x){
        n=x;
        for(int i=1;i dis(n+1,1e18),vis(n+1,0);
        priority_queue> 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>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>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>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>w;
        g.add(id(i,j,0),id(i,j,1),w);
    }
    cout

`#include
using namespace std;
#define int long long
const int N=2e6+5;

struct graph{
    int n;
    vectorpairint,int>> g[N];
    void init(int x){
        n=x;
        for(int i=1;in;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){
        vectorint> dis(n+1,1e18),vis(n+1,0);
        priority_queuepairint,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]+wdis[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;in;i++) for(int j=1;jm-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;in-1;i++) for(int j=1;jm;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;in-1;i++) for(int j=1;jm-1;j++){
        cin>>w;
        g.add(id(i,j,0),id(i,j,1),w);
    }
    coutg.dij(s,t);
    return 0;
}`