P3227

jijidawang · 2022-09-10 20:05:59 · 题解

广义切糕模型之最小割离散变量模型

Preface

2016 年的候选队论文《网络流的一些建模方法》（姜志豪）给出了一种最小割建模方法——最小割离散变量模型 .

以下 \infty 均为正无穷 .

Solution

最小割离散变量模型

建图方式一般就是对每个变量 $x_i$ 拆成 $m_i+1$ 个点串成一个源点 $s$ 到汇点 $t$ 的链，割哪条边就代表取那个值，贡献用两条链直接的连边表达，于是就变成最小割形式了 .

对于这个题，对于每个点 (i,j)，其中 1\le i\le P,1\le j\le Q，就相当于有一个变量 x_{i,j}，取值为对于 1\le k\le R 的不和谐值 v(i,j,k) .

注意到有一个光滑度限制，注意到最小割中 \infty 边不可能被选，那么我们可以借助一条 \infty 边 u\overset{\infty}{\to} v，来限制 s,u 和 v,t 不同时连通 .

于是我们对每个点向周围能连的最远点连一条 \infty 边就可以解决问题了，可以画一下这个图的样子，一个可行的最小割必然对应一组可行最优解 .

建图建好了直接跑最小割即可，时间复杂度就是最小割复杂度 .

「开门大吉」一题给出了一个更一般的问题，可以尝试做一下 .

Code

dinic F;
int p, q, r, d, v[L][L][L];
inline int node(int i, int j, int k){return i * 1600 + j * 40 + k;}
int main()
{
    scanf("%d%d%d%d", &p, &q, &r, &d); int s = 1, t = 2;
    for (int k=1; k<=r; k++)
        for (int i=1; i<=p; i++)
            for (int j=1; j<=q; j++) scanf("%d", v[i][j] + k);
    for (int i=1; i<=p; i++)
        for (int j=1; j<=q; j++)
        {
            F.addedge(s, node(i, j, 1), v[i][j][1]); F.addedge(node(i, j, r), t, INF);
            for (int k=2; k<=r; k++) F.addedge(node(i, j, k-1), node(i, j, k), v[i][j][k]);
        }
    for (int i=1; i<=p; i++)
        for (int j=1; j<=q; j++)
            for (int k=1; k<=r-d; k++)
            {
                if (inrange(i+1, 1, p)) F.addedge(node(i+1, j, k+d), node(i, j, k), INF);
                if (inrange(i-1, 1, p)) F.addedge(node(i-1, j, k+d), node(i, j, k), INF);
                if (inrange(j+1, 1, q)) F.addedge(node(i, j+1, k+d), node(i, j, k), INF);
                if (inrange(j-1, 1, q)) F.addedge(node(i, j-1, k+d), node(i, j, k), INF);
            }
    printf("%lld\n", F.maxflow(s, t));
    return 0;
}