关于网络流及最大匹配简单题建模的一些总结

· · 算法·理论

关于代码的说明

显然代码不是重点，所以只保留核心代码。

但是模板题会保留算法的代码参考。

其实有些题目我直接懒得放了，相信各位大神可以写出来。

文章写作时间跨度较大，所以码风会有些不同。

最大流

最典型的一个问题，也就是网络流的模板题了。

例 1.1 草地排水

给出 n 个点，m 条边的有向图，每个边有一个容量，给出一个起点和终点，求起点可以向终点流多少水。

这就是一个典型的最大流问题了，直接使用 Dinic 算法即可

bool bfs(LL x) {
    memset(dep, 0, sizeof(dep));
    while (!q.empty()) q.pop();
    q.push(x);
    dep[x] = 1;
    while (!q.empty()) {
        LL t = q.front();
        q.pop();
        for (LL i = h[t]; i; i = a[i].nxt) {
            if (!a[i].w || dep[a[i].to])continue;
            dep[a[i].to] = dep[t] + 1;
            q.push(a[i].to);
        }
    }
    if (dep[t]) {
        for (int i = 1; i <= n; i++) cur[i] = h[i];
        return 1;
    }
    return 0;
}
LL dfs(LL x, LL f) {
    if (x == t || !f)return f;
    LL ans = 0;
    for (LL i = cur[x]; i; i = a[i].nxt) {
        if (!f)continue;
        LL y = a[i].to;
        cur[x] = i;
        if (dep[y] != dep[x] + 1)continue;
        LL k = dfs(y, min(f, a[i].w));
        if (k)ans += k, f -= k, a[i].w -= k, a[i ^ 1].w += k;
    }
    return ans;
}
LL dinic() {
    LL ans = 0;
    while (bfs(s)) ans += dfs(s, inf);
    return ans;
}
int main() {
    scanf("%lld%lld", &m, &n);
    s = 1, t = n;
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w), add(v, u, 0);
    }
    printf("%lld\n", dinic());
}

例 1.2 成语接龙问题

你有 n 个成语，你可以进行无数轮游戏（如果可以），一轮游戏过程如下：

  • 选择一个没有成语可以接到的成语。
  • 不断转移到当前成语下一个可以接到的成语。
  • 在一个不能接到任何成语的成语停止。

这里的成语指的是由四个有序的数字的构成的一个四元组。

一个成语可以接到一个成语当且仅当前面的成语的最后一个数字等于后面的成语的第一个数字。

对于每个成语，有一个使用限制次数，不能使用更多次求最多可以进行几次游戏。

我们不难把对每个词语转换成一条边，点就是第一个数字和最后一个数字。

然后，对于没有成语可以接到的成语，源点与其连边，不能接到任何成语的成语，与汇点连边，容量为无穷大。

限制次数不难看作是容量，一次游戏相当于流了一个流量为 1 的路径，所以答案就是最大流。

scanf("%lld%lld",&n,&m);
s=n+1,t=n+2;
for(int i=1;i<=m;i++)
{
    scanf("%lld%lld%lld%lld%lld",&x,&b,&c,&y,&w);
    add(x,y,w),du[x][0]++,du[y][1]++;
}
for(int i=1;i<=n;i++)if(du[i][1]==0&&du[i][0])add(s,i,inf);
for(int i=1;i<=n;i++)if(du[i][0]==0&&du[i][1])add(i,t,inf);
printf("%lld",dinic());

例 1.3 危桥问题

有 N 座岛，有些岛之间有桥相连，桥是双向的。

Alice 希望在岛屿 a_1 和 a_2 之间往返 a_n 次，Bob 希望在岛屿 b_1 和 b_2 之间往返 b_n 次。

这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。

求 Alice 和 Bob 是否能完成任务。

类似于成语接龙问题，容易想到用容量表示可以走的次数，问题是，这题有两个源点，两个汇点，每个源点流向唯一的汇点。

考虑建一个超级源点，把两个源点连到超级源点上，容量为 a_n,b_n，超级汇点同理。

最后看最大流是否为 a_n+b_n 即可。

但这样是不对的，并没有保证 a_1\to a_2，b_1\to b_2，所以可能出现 a_1\to b_2,b_1\to a_2 的贡献。

怎么办？

考虑交换 b_1,b_2，以 b_2 为源点再跑一次网络流，看看是否是满的。

必要性是显然的，让我们来看看充分性：

设原来 a_1\to b_2 的流量为 x，显然，a_1\to a_2 的流量为 a_n-x，b_1\to a_2 的流量为 x，b_1\to b_2 的流量为 b_n-x。

反转之后，如果可以满流，那么存在方法使 a_1\to a_2 的流量可以不变为 a_n-x，b_2\to b_1 的流量可以不变为 b_n-x，显然，存在方法使 a_1\to b_1 的流量为 x，存在方法使 b_2\to a_2 的流量为 x。

然后你就发现存在路径 b_1\to a_1\to b_2 的流量为 x，把这一部分流量留过去就行了。

while(cin>>n>>a>>b>>t1>>c>>d>>t2)
{
    tot=1;
    a++,b++,c++,d++;
    memset(h,0,sizeof(h));
    memset(H,0,sizeof(H));
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char c;
            cin>>c;
            if(c=='X')continue;
            if(c=='N')add(i,j,inf);
            if(c=='O')add(i,j,1);
        }
    }
    for(int i=2;i<=tot;i++)B[i]=A[i];
    for(int i=1;i<=n+2;i++)H[i]=h[i];
    add(n+1,a,t1),add(n+1,c,t2);
    add(b,n+2,t1),add(d,n+2,t2);
    LL t=dinic(n+1,n+2);
    if(t!=t1+t2)
    {
        puts("No");
        continue;
    }

    for(int i=2;i<=tot;i++)A[i]=B[i];
    for(int i=1;i<=n+2;i++)h[i]=H[i];   
    tot-=4;
    add(n+1,a,t1),add(n+1,d,t2);
    add(b,n+2,t1),add(c,n+2,t2);
    t=dinic(n+1,n+2);
    if(t!=t1+t2)
    {
        puts("No");
        continue;
    }
    puts("Yes");
}

最小割

最小割指在网络流模型中，花费最小的代价使得源点与汇点不连通。

有一个定理，最小割就是最大流。这个怎么证明呢？自己找资料吧......

例 2.1 追查坏牛奶

有一批问题牛奶从源点发往汇点，拦截代价最小的边使得牛奶无法送往汇点，最小代价为多少？拦截几条边？哪几条边？

对于多种方案，希望边数最小，边数相等则希望字典序。

这显然就是一个最小割问题，其难点其实是后两问。

考虑找一个大于边数的值k,建议为k=1007，然后原边权为x，则现在的边权为xk+1。

跑完最大流之后，因为边数不会超过k，所以答案整除k 的结果就是原答案，而模 k 就是边数。

对于方案输出的奇葩要求，我们发现经过如上处理的答案本身就是边数最小的方案。

因为模k后的部分表示边数，它包含在答案之中，整除k的部分相等情况下，边数更小的成为了答案。

接下来枚举边，对于每条边，计算删边之后的最小割，如果删边后的答案加上它的边权为原答案，这条边就是答案中的边。

注意，如果这是答案中的边，请在答案中减去这一部分，并且以后也不要恢复，防止多种方案杂糅在一起。

scanf("%lld%lld", &n, &m);
s = 1, t = n;
for (int i = 1; i <= m; i++) {
    scanf("%lld%lld%lld", &u, &v, &w);
    add(u, v, w * mod + 1), add(v, u, 0);
}
for (int i = 2; i <= tot; i++)b[i] = a[i];
LL ans = dinic();
printf("%lld %lld\n", ans / mod,  ans % mod);
for (int i = 1; i <= tot; i++)c[i] = a[i];
for (int i = 2; i <= tot; i += 2) {
    for (int j = 2; j <= tot; j++)if (a[j].f == 0)a[j] = b[j];
    a[i].w = 0;
    LL tmp = dinic();
    if (tmp + b[i].w == ans) {
        cout << i / 2 << endl;
        a[i].f=1,a[i^1].f=1,ans -= b[i].w;
    }
}

例 2.2 文理分科问题

班级要进行文理分科，班级可以用一个 n\times m 的矩阵进行描述，每个格子代表一个同学的座位。

每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

  • 如果第 i 行第 j 列的同学选择了文科，则他将获得 A_{i,j} 的满意值，如果选择理科，将得到 S_{i,j} 的满意值。

  • 如果第 i 行第 j 列的同学选择了文科，并且他相邻的同学全部选择了文科，则他会更开心，所以会增加 SA_{i,j} 的满意值。

  • 如果第 i 行第 j 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 SS_{i,j} 的满意值。

最小割可以用来处理一些带贡献的变量之间有约束的问题，通常有以下构造方法：

先不考虑相邻的贡献，那么我们得到这个模型的最基础的样子：源点表示选择文科，汇点表示选择理科，中间每个点表示一个同学，每个点连向源点汇点，容量分别为 A_{i,j},S_{i,j}。

接下来考虑相邻，以文科相邻为例：

对于每个点建一个点表示”与其相邻的点“，这个点连向源点，容量为 SA_{i,j}，同时表示约束，连向相邻点和自己，表示约束，容量应该无穷大。

这样这条路不联通只有两种可能：

bool pd(LL x,LL y)
{
    return 1<=x&&x<=n&&1<=y&&y<=m;
}
const LL dx[4]={0,0,1,-1};
const LL dy[4]={1,-1,0,0};
int main()
{
    cin>>n>>m;
    LL s=3*n*m+1,t=3*n*m+2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            LL x;
            cin>>x;
            sum+=x;
            add(s,(i-1)*m+j,x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            LL x;
            cin>>x;
            sum+=x;
            add((i-1)*m+j,t,x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            LL x;
            cin>>x;
            sum+=x;
            add(s,n*m+(i-1)*m+j,x);
            add(n*m+(i-1)*m+j,(i-1)*m+j,inf);
            for(int k=0;k<4;k++)
            {
                LL xx=i+dx[k],yy=j+dy[k];
                if(!pd(xx,yy))continue;
                add(n*m+(i-1)*m+j,(xx-1)*m+yy,inf);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            LL x;
            cin>>x;
            sum+=x;
            add(2*n*m+(i-1)*m+j,t,x);
            add((i-1)*m+j,2*n*m+(i-1)*m+j,inf);
            for(int k=0;k<4;k++)
            {
                LL xx=i+dx[k],yy=j+dy[k];
                if(!pd(xx,yy))continue;
                add((xx-1)*m+yy,2*n*m+(i-1)*m+j,inf);
            }
        }
    }
    cout<<sum-dinic(s,t)<<endl;
}

最大匹配问题

最大匹配问题是二分图匹配的一个问题，这也是最基础，最简单的一类问题。

直接使用匈牙利算法，赢！

当然，也可以使用网络流算法，比如 Dinic 算法，时间复杂度在此情况下十分优秀。

具体如何建图？考虑建一个超级源点 u 和一个超级汇点 v ，超级源点向 X 部的点流一条容量为 1 的边，Y 部的点向超级汇点流一条容量为 1 的边。

对于原来的二分图，处理之后大概长这样：

例 3.1 飞行员配对问题

有m个主飞行员与n-m个副飞行员，只有两人愿意才能配对，求最大配对数。

这是一道很明显的最大匹配问题,也算是匈牙利算法的模板题。

主飞行员和副飞行员可以变成二分图的两个部分，若有两人愿意配对则连边，然后求最大匹配即可。

int choose(int x)
{
    for(int i=m+1;i<=n;i++)
    {
        if(a[x][i]==0 || vis[i]==1)continue;
        vis[i]=1; 
        if(c[i] == 0 || choose(c[i]))
        {
            c[i]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>m>>n;
    while(x!=-1&&y!=-1)
    {
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof(vis));
        if(choose(i))ans++;
    }
    cout<<ans<<endl;
}

例 3.2 火力网

给出一个 n\times n 的地图，要求放最多的无法互相攻击的炮台，炮台的攻击范围是一行加上一列，遇到障碍物为止。

这道题看着是一道最大独立集问题，其实我们发现这个攻击范围很大，无法转换成一个二分图，因此与下面的骑士共存问题做法不同。

我们发现放置一个炮台刚好会消掉一个连续的横排和竖列，我们把所有的连续的横排和竖列变成点。

然后，有交点的横排和竖列连上边，这样显然是二分图。建模之后，因为我们希望尽可能多地消除横排和竖列，本质上就是匹配横排和竖列。

因此，这个问题其实是一个最大匹配问题。

memset(b, -1, sizeof(b));
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        cin >> ch;
        if (ch == 'X')b[i][j] = 1, m++;
        else b[i][j] = 0;
    }
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (b[i][j])continue;
        if (b[i][j - 1] == 0)num[i][j] = cnt;
        else num[i][j] = ++cnt;
    }
cnt2 = cnt;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (b[j][i] == 1)
            continue;
        if (b[j - 1][i] == 0)num2[j][i] = cnt;
        else num2[j][i] = ++cnt;
}
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)if (b[i][j] == 0)b2[num[i][j]][num2[i][j]] = 1;
for (int i = 1; i <= cnt; i++)
    for (int j = 1; j <= cnt; j++)if (b2[i][j])add(i, j), add(j, i);
for (int i = 1; i <= cnt2; i++) {
    if (c[i])continue;
    memset(vis, 0, sizeof(vis));
    if (choose(i))ans++;
}
printf("%lld", ans);

例 3.3 最小路径覆盖问题

使用最少的简单路径覆盖一个 n 个点，m 条边的有向无环图，要求路径之间没有交点。

这依旧是一个最大匹配问题。

注意到对于一个点 i,只可能有一个点连向它，它也只会连向一个点。

首先这里有一个肥肠有用的技巧——将 n 个点分成 2n 个点，i 点属于二分图的左半部分，表示 i “走出去”的点，i+n 点属于二分图的右半部分，表示 i “走进来”的点。

这就有了一个二分图，接下来我们做一个转换，假设两个点相连等同于合并，那么我们希望最后剩下的点最少，而每次合并恰好删除一个点。

也就是说，我们希望匹配越多越好，这就变成了最大匹配问题。

答案就是点数减去最大匹配。

void dg(LL x, LL lst) {
    if (x == 0)return;
    if (x <= n)x += n;
    if (c[x] != lst)dg(c[x], x);
    x -= n;
    vis[x] = 1;
    printf("%lld ", x);
    if (c[x] != lst)dg(c[x], x);
    if (lst == 0)printf("\n");
}
int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &x, &y);
        add(x, y + n);
    }
    for (int i = 1; i <= n; i++) {
        if (c[i])continue;
        memset(vis, 0, sizeof(vis));
        if (choose(i))ans++;
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)if (!vis[i])dg(i, 0);
    printf("%lld", n - ans);
}

例 3.4 试题库问题

有 n 道题,每道题都属于一些类别现要从中选 m 道题组成试卷。

给出试卷包含指定类型的试题及对应的数量，设计一个满足要求的方案。

是最大匹配吗？是，但是也不是，我们要用网络流写。

这道题可以将题目转换为二分图的左边，题目类型转换为右边，连边方式与上文介绍的转换方式无异。

注意到题目类型对应多个题目，可以理解为“一夫多妻”，那么我们如何处理这个问题。

我们思考原先的建图如何做到一一对应，不难发现，无论如何，右边连接汇点的容量都为 1。

也就是说，无论有多少左边的点选择了一个右边的点，造成的贡献都只有 1。

受到启发，我们将右边的点连向汇点的容量设为需要的题目数量即可。

for(int i=1;i<=n;i++)
{
    scanf("%lld",&x);
    sum+=x,add(i,t,x);
} 
for(int i=1;i<=m;i++)add(s,n+i,1);
for(int i=1;i<=m;i++)
{
    scanf("%lld",&x);
    while(x--)
    {
        scanf("%lld",&y);
        add(n+i,y,1);
    }
}
LL cnt=dinic(s,t);
if(cnt!=sum)
{
    puts("No Solution!"); 
    return 0;
} 
for(int i=2;i<=tot;i+=2)
{
    LL x=a[i^1].to,y=a[i].to;
    if(x==s||x==t||y==s||y==t)continue;
    if(x>y)swap(x,y);
    if(a[i].w==0)v[x].push_back(y-n);
}
for(int i=1;i<=n;i++)
{
    printf("%lld:",i);
    sort(v[i].begin(),v[i].end());
    for(auto j:v[i])printf("%lld ",j); 
    printf("\n");
}

最小点覆盖问题

最小点覆盖指的是如何选择最少的点，使得所有边都至少有一端被选择。

有一个结论：最大匹配等于最小点覆盖。

结论证明

必要性：最小点覆盖怎么说都应该大于等于最大匹配，这点显然，欢迎感性理解。

充分性：考虑反证法，若在某个最大匹配方案中存在一边两端都没被选择，则这条边可以被匹配，这与这个匹配是最大匹配矛盾。

由此得证。

最大独立集问题

我们有一个定理：二分图的最大独立集的大小等同于顶点数减去最小点覆盖（感性理解来看，这两个东西是刚好反过来的，一个是最小的全部连接，一个是最大的全部断开）。

而最小点覆盖等同于最大匹配，所以问题就解决了。

这种题目还是蛮明显的，通常是棋盘上的共存问题，下面的两道题就是例子。

例 5.1 骑士共存问题

给一个 n\times n 的棋盘和棋盘上有 m 个不能走的地方，请问最多可以放多少个互相无法攻击的骑士？

骑士的走法可以理解为中国象棋的马。

不得不说网络流24题质量还是非常高的，这是我人生中的第二道网络流24题。

当然是看了题解的......

首先，根据观察，我们发现棋盘可以分成两部分。

如 n=5 时，可以分成：

\begin{aligned} \tt{01010}\\ \tt{10101}\\ \tt{01010}\\ \tt{10101}\\ \tt{01010}\\ \end{aligned}

显然，两个部分，同一个部分的点无法互相攻击，正像二分图，同一部分不连边。

于是，我们可以建图，发现是一个二分图。

而本题要求骑士最多，本质上是一个最大独立集。

const LL dx[8]={1,1,2,2,-1,-1,-2,-2};
const LL dy[8]={2,-2,1,-1,2,-2,1,-1};
void link(LL x,LL y)
{
    if(b[x][y])return;
    for(int i=0;i<8;i++)
    {
        LL xx=x+dx[i],yy=y+dy[i];
        if(1<=xx&&xx<=n&&1<=yy&&yy<=n&&b[xx][yy]==0)add(num[x][y],num[xx][yy]),add(num[xx][yy],num[x][y]);
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        b[x][y]=1;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)num[i][j]=++cnt;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)link(i,j);
    for(int i=1;i<=cnt;i++)
    {
        if(c[i])continue;
        memset(vis,0,sizeof(vis));
        if(choose(i))ans++;
    }
    printf("%lld",cnt-m-ans); 
}

例 5.2 国际跳棋问题

有一个 n\times n 的棋盘，有 m 个障碍物，每个棋子的攻击范围是左上，左下，右上，右下。

求最多放置多少个互不侵犯的棋子。

这道题是 DeepSeaSpray 老师生日赛的题目。

我们分析一下，不难发现，对于 (x,y)，我们可以根据 x+y 的奇偶性来分成两部分。

同部分无法互相攻击，所以是和其实骑士共存问题很像的。

由于代码十分相像，只需修改 dx,dy 两个常量数组即可。

方格取数问题

每个元素是有权值的，你需要在其中取数。

同时，题目往往会有一些限制条件，表示出它们的影响是我们建模的关键。

通常的套路是，通过转换和建图，使答案为格子权值的总和减去最小割。

格子间会有一些限制条件，我们建图的时候要好好思考如何将这些条件融合在网络流模型之中。

例 6.1 方格取数问题

有一个 n\times m 的矩阵，其中间取数，要求相邻的格子不可以同时取，请问最大值为多少？

我们黑白染色，分成两种方格，然后相邻格子连边。

显然此时恰好分成两边。

接下来，左边与源点连边，右边与汇点连边，容量为格子的权值。

其实发现就是最大独立集加个权值，跑出一个最小割，可以理解为是最小点覆盖，所以答案是总和减去最小割。

s=n*m+1,t=n*m+2;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        scanf("%lld",&x);
        if((i+j)%2==0)
        {
            add(s,num(i,j),x);
            for(int k=0;k<4;k++)
            {
                LL xx=i+dx[k],yy=j+dy[k];
                if(xx<1||n<xx||yy<1||m<yy)continue;
                add(num(i,j),num(xx,yy),inf);
            }
        }
        else add(num(i,j),t,x);
        sum+=x;
    } 
}
printf("%lld",sum-dinic(s,t));

例 6.2 X 画线取数问题

有一个 n\times m 的矩阵，其中间取数。

你需要选择一些格子，你的所得就是选择的格子的权值之和减去将这些格子画 X 的花费。

具体地，你可以在每个格子内部画线，可以从左上到右下，也可以从左下到右上，花费是总画线数乘上一个常量 C。

比如，你可以用三笔画出格子 (1,1),(2,2) 上的 X，从 (1,1) 的左上角到 (2,2) 的右下角；从 (1,1) 的右上角到 (1,1) 的左下角，从 (2,2) 的右上角到 (2,2) 的左下角。

求最大所得。

首先我们转换问题，考虑到网络流处理方格取数问题的套路是格子权值的总和减去最小割，我们怎么往上靠？

根据套路的式子，我们用总和减去答案易得最小割所求：

选的格子的权值加上不选的格子的权值减去选的格子的权值加上划线的代价。

这个过程有所抵消，化简得到：

不选的格子的权值加上划线的代价，这就是我们要使其最小的代价了。

这个转换有什么用处呢？我们发现原问题有加有减很烦，这个问题只有加。

首先显然每个格子 (i,j) 都应该向源点连边，容量为 a_{i,j}，这表示出了每个格子基本的选和不选，如果不选，这条边会被割掉。

然后我们要考虑画 X 这一条件。

发现，对于一条连续选择的斜线，如果有一个格子画了这个方向相反的线，其他的格子就不用画了。

我们将所有存在斜线前一项的格子向前一项连一条容量为 C 的边，只要某个斜线有一个边断开，其他的边自然无法从此方向到达汇点。

如果前一项的格子不存在，则向汇点连一条权值为 C 的边。

于是答案就是格子权值的总和减去最小割。

scanf("%lld%lld%lld",&n,&m,&c);
LL s=n*m+1,t=n*m+2; 
for(int i=1;i<=n;i++) 
{
    for(int j=1;j<=m;j++)
    {
        scanf("%lld",&x);
        sum+=x;
        add(s,num(i,j),x);
        if(i!=1&&j!=1)add(num(i,j),num(i-1,j-1),c);
        else add(num(i,j),t,c);
        if(i!=n&&j!=1)add(num(i,j),num(i+1,j-1),c);
        else add(num(i,j),t,c);
    }
}
printf("%lld",sum-dinic(s,t));

二分图博弈论

通常此类题目给出一个矩阵，棋盘之类的东西，我们可以转换为二分图，接下来是一个博弈问题。

先手将点移动一步，后手再将点移动一步，一个点只能到达一次，反复操作，不可操作者败。

我们有结论：一个起点可以使先手必胜，当且仅当这个点出现在所有的最大匹配方案中。

结论证明

两者持续进行游戏，其路径可以看作一条增广路，由于双方决策都是最佳，我们希望增广路越长越好。

我们设增广路为 a_1\to a_2 \to a_3 \to...\to a_n。

有了上述铺垫，可以开始证明。

必要性：

如果存在一个点不在所有的最大匹配方案中但是必胜，后手可以走其不为最大匹配的方案，直到有一个失配点 a_{n+1}。

如果先手还能走，那么这个失配点也一定可以再匹配，这与我们已知的最大匹配矛盾。

充分性：

如果一个点出现在所有的最大匹配方案中，后手无论怎么走，先手都可以走到其匹配点，后手一定走不到失配的点。

因为我们可以设新走到的点为 a_{n+1}，则我们有最大匹配方案 a_2 \to a_3 \to...\to a_n \to a_{n+1}。

这与这个点出现在所有的最大匹配方案中矛盾。

由此证明完成。

例 7.1 游戏

有一棋盘，有些点可以走，有些不可走，双方轮流走，不可走重复的点，不可操作者败。

有哪些多少先手必胜的起点。

这道题我们考虑对棋盘黑白染色，这样可以形成一个二分图，相邻的点连双向边。

先跑一次最大匹配备用。

然后跑二分图博弈论即可，对于每个点，判断其是否出现在所有的最大匹配方案的方法是尝试让其配对的点“另寻新欢”，看看是否存在方案。

这道题数据很水，所以我的通过代码可能没有处理一些情况。

const LL dx[2] = { 0, -1 };
const LL dy[2] = { -1, 0 };
void link(LL x, LL y) {
    for (int i = 0; i < 2; i++) {
        LL xx = x + dx[i], yy = y + dy[i];
        if (xx == 0 || yy == 0 || xx == n + 1 || yy == m + 1)
            continue;
        if (c[xx][yy] == '.') {
            add(x, y, xx, yy);
            add(xx, yy, x, y);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", c[i] + 1);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '#')
                continue;
            link(i, j);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '#')
                continue;
            if (f[i][j][1] == 1)
                continue;
            memset(vis, 0, sizeof(vis));
            if (f[i][j][1] == 0)
                dfs(i, j);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '.') {
                memset(vis, 0, sizeof(vis));
                if (f[i][j][0] == 0 || dfs(f[i][j][0], f[i][j][1]))
                    printf("%d %d\n", i, j);
            }
        }
    }
}

例 7.2 兔兔与蛋蛋的游戏

一个棋盘上的博弈游戏，先后手轮流操作，初始时每个格子都有一个棋子，只有一个位置是空位。

先手可以将空位与相邻的某个白子交换位置，后手可以将空位与相邻的某个黑子交换位置。

若不可操作则败北。

给出双方的操作，求先手有哪些操作失误了。

本题有一个隐藏条件，就是一个格子只能走一次，这是因为离开再回来一定是偶数步，而颜色变换无法移动至原位。

首先我们把目光聚焦在这个空格上，我们发现其走的棋子的颜色恰好是每次变换的，由于开始走的是白色，我们可以认为初始空格为黑色。

我们将相邻的不同颜色的棋子建边，不难发现其走的是一个二分图。

我们对于每个操作都看看是否移动到了先手必胜点，保存下来。

然后看看先手的每次操作，如果操作前必胜，操作后还是必胜，那就是失误了。

const LL dx[4]={0,0,-1,1};
const LL dy[4]={1,-1,0,0};
LL num(LL x,LL y)
{
    return (x-1)*m+y;
}
bool pd(LL x,LL y)
{
    if(x<1||n<x||y<1||m<y||s[x][y]!='O')return false;
    return true;
}
vector<LL>v[N],ans;
LL link(LL x,LL y)
{
    for(int i=0;i<4;i++)
    {
        LL xx=x+dx[i],yy=y+dy[i];
        if(!pd(xx,yy))continue;
        add(num(x,y),num(xx,yy));
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            if(s[i][j]=='.')x=i,y=j;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='O')continue;
            link(i,j);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='O')continue; 
            memset(vis,0,sizeof(vis));
            choose(num(i,j));
        }
    LL k;
    cin>>k;
    for(int i=1;i<=2*k;i++)
    {
        LL t=num(x,y);
        cin>>x>>y;
        fgt[t]=1;
        if(c[t]==0)continue;
        LL nxt=c[t];
        c[t]=c[nxt]=0;
        memset(vis,0,sizeof(vis));
        if(!choose(nxt))win[i]=1;

    }
    for(int i=1;i<=k;i++)
        if(win[2*i-1]==1&&win[2*i]==1)ans.push_back(i);
    cout<<ans.size()<<endl;
    for(auto i:ans)cout<<i<<endl;
}

最佳匹配

最佳匹配在最大匹配的基础上为边添加了权值的概念，可以使用 KM 算法。

也可以转换为最大费用最大流，建图方式同最大匹配，边权为网络流中的费用。

题目出处

本文引用了大量题目，部分题目略作修改，题目大多经过本人简化。

以下是部分题目来源：

如有缺少，欢迎补充。