[C++知识库]P4003 无限之环

题面自己看吧。。。

std

对于这种毒瘤的最小费用匹配问题，一般考虑网络费用流。

对于每个水管的每一个支管，有且仅有一个其它方格上的水管的其中一个支管与其相连，这样就不会漏水了，也就是一个水管的每个支管容量只能为 $1$，且都要满流。

由于我们要用网络流，又考虑到只有相邻的两个水管又可能产生流量，于是考虑将图黑白染色。

这样黑点只能连向白点，白点只能连向黑点。

然后将一个方格拆成 $5$ 个点，分别表示上下左右中。

模型建立

$s$ 向白点的中点连一条容量为支管数量，费用为 $0$ 的边。

黑点的中点向 $t$ 连一条容量为支管数量，费用为 $0$ 的边。

根据支管情况向四周连容量为 $1$，费用为 $0$ 的边。

然后分水管的情况讨论：

1

上点分别向左，右点向一条容量为 $1$，费用为 $1$ 的边（转 $90$ 度）。

上点向下点连向一条容量为 $1$，费用为 $2$ 的边（转 $180$ 度）。

2

由于不用旋转，那么只需让中点分别向上、下点连一条容量为 $1$，费用为 $0$ 的边（上面说过了）。

3

顺时针转 $90$ 度，会变成这样：

这相当于原来的上点变成了下点，右点不变，那么让上点向下点连一条容量为 $1$，费用为 $1$ 的边即可。

逆时针转 $90$ 度同理，让右点向左点连一条容量为 $1$，费用为 $1$ 的边即可。

转 $180$ 度，会变成这样：

这相当于，你将前面说的两条边一起用了。

4

顺时针转 $90$ 度，会变成这样：

这相当于上、右点不变，左点变成了下点，于是让左点向下点连一条容量为 $1$，费用为 $1$ 的边即可。

逆时针转 $90$ 度同理，让右点向下点连一条容量为 $1$，费用为 $1$ 的边即可。

转 $180$ 度，会变成这样：

这相当于左、右点不变，上点变成了下点，于是让上点向下点连一条容量为 $1$，费用为 $2$ 的边即可。

5

由于这转了相当于没转，那么不管他。

$\text{231ms?/?1.71MB?/?7.49KB?C++20?O2}$。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

typedef int tp;

const int _ = 6e4 + 10, inf = 947483647;

int n, m, s, t, lv[_], cur[_];

tp maxflow, mincost;

int tot = 1, head[_], to[_ << 1], nxt[_ << 1];

tp dis[_], w[_ << 1], fl[_ << 1];

inline void add(int u, int v, tp dis, tp c)
{
    to[++tot] = v;
    nxt[tot] = head[u];
    fl[tot] = dis;
    w[tot] = c;
    head[u] = tot;
}

inline void Add(int u, int v, tp dis, tp c)
{
    add(u, v, dis, c);
    add(v, u, 0, -c);
}

inline bool bfs()
{
    memset(lv, 0, sizeof(lv));
    for (int i = 0; i < _; ++i)
        dis[i] = inf;
    lv[s] = 1;
    dis[s] = 0;
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        lv[p] = 0;
        for (int eg = head[p]; eg; eg = nxt[eg])
        {
            int v = to[eg];
            tp vol = fl[eg];
            if (vol > 0 && dis[v] > dis[p] + w[eg])
            {
                dis[v] = dis[p] + w[eg];
                if (!lv[v])
                {
                    q.push(v);
                    lv[v] = 1;
                }
            }
        }
    }
    return dis[t] != inf;
}

tp dfs(int p = s, tp flow = inf)
{
    if (p == t)
        return flow;
    lv[p] = 1;
    tp rmn = flow;
    for (int eg = cur[p]; eg && rmn; eg = nxt[eg])
    {
        cur[p] = eg;
        int v = to[eg];
        tp vol = fl[eg];
        if (vol > 0 && !lv[v] && dis[v] == dis[p] + w[eg])
        {
            tp c = dfs(v, min(vol, rmn));
            rmn -= c;
            fl[eg] -= c;
            fl[eg ^ 1] += c;
        }
    }
    lv[p] = 0;
    return flow - rmn;
}

inline void dinic()
{
    while (bfs())
    {
        tp flow = dfs();
        maxflow += flow;
        mincost += dis[t] * flow;
    }
}

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

int sum;

const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}, cross[] = {3, 4, 1, 2};

inline void build(int x, int y, int num)
{
    if ((x + y) & 1)
    {
        Add(s, id(x, y, 0), 1 << 30, 0);
        for (int i = 0; i < 4; ++i)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx <= 0 || xx > n || yy <= 0 || yy > m)
                continue;
            Add(id(x, y, i + 1), id(xx, yy, cross[i]), 1, 0);
        }
        for (int i = 0; i < 4; ++i)
            if (num & (1 << i))
            {
                Add(id(x, y, 0), id(x, y, i + 1), 1, 0);
                ++sum;
            }
        switch (num)
        {
        case 1:
            Add(id(x, y, 1), id(x, y, 2), 1, 1);
            Add(id(x, y, 1), id(x, y, 3), 1, 2);
            Add(id(x, y, 1), id(x, y, 4), 1, 1);
            break;
        case 2:
            Add(id(x, y, 2), id(x, y, 1), 1, 1);
            Add(id(x, y, 2), id(x, y, 3), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 2);
            break;
        case 4:
            Add(id(x, y, 3), id(x, y, 1), 1, 2);
            Add(id(x, y, 3), id(x, y, 2), 1, 1);
            Add(id(x, y, 3), id(x, y, 4), 1, 1);
            break;
        case 8:
            Add(id(x, y, 4), id(x, y, 1), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 2);
            Add(id(x, y, 4), id(x, y, 3), 1, 1);
            break;
        case 3:
            Add(id(x, y, 1), id(x, y, 3), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 1);
            break;
        case 6:
            Add(id(x, y, 3), id(x, y, 1), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 1);
            break;
        case 9:
            Add(id(x, y, 1), id(x, y, 3), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 1);
            break;
        case 12:
            Add(id(x, y, 3), id(x, y, 1), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 1);
            break;
        case 7:
            Add(id(x, y, 1), id(x, y, 4), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 2);
            Add(id(x, y, 3), id(x, y, 4), 1, 1);
            break;
        case 11:
            Add(id(x, y, 1), id(x, y, 3), 1, 2);
            Add(id(x, y, 2), id(x, y, 3), 1, 1);
            Add(id(x, y, 4), id(x, y, 3), 1, 1);
            break;
        case 13:
            Add(id(x, y, 1), id(x, y, 2), 1, 1);
            Add(id(x, y, 3), id(x, y, 2), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 2);
            break;
        case 14:
            Add(id(x, y, 2), id(x, y, 1), 1, 1);
            Add(id(x, y, 3), id(x, y, 1), 1, 2);
            Add(id(x, y, 4), id(x, y, 1), 1, 1);
            break;
        }
    }
    else
    {
        Add(id(x, y, 0), t, 1 << 30, 0);
        for (int i = 0; i < 4; ++i)
            if (num & (1 << i))
            {
                Add(id(x, y, i + 1), id(x, y, 0), 1, 0);
                ++sum;
            }
        switch (num)
        {
        case 1:
            Add(id(x, y, 2), id(x, y, 1), 1, 1);
            Add(id(x, y, 3), id(x, y, 1), 1, 2);
            Add(id(x, y, 4), id(x, y, 1), 1, 1);
            break;
        case 2:
            Add(id(x, y, 1), id(x, y, 2), 1, 1);
            Add(id(x, y, 3), id(x, y, 2), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 2);
            break;
        case 4:
            Add(id(x, y, 1), id(x, y, 3), 1, 2);
            Add(id(x, y, 2), id(x, y, 3), 1, 1);
            Add(id(x, y, 4), id(x, y, 3), 1, 1);
            break;
        case 8:
            Add(id(x, y, 1), id(x, y, 4), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 2);
            Add(id(x, y, 3), id(x, y, 4), 1, 1);
            break;
        case 3:
            Add(id(x, y, 3), id(x, y, 1), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 1);
            break;
        case 6:
            Add(id(x, y, 1), id(x, y, 3), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 1);
            break;
        case 9:
            Add(id(x, y, 3), id(x, y, 1), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 1);
            break;
        case 12:
            Add(id(x, y, 1), id(x, y, 3), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 1);
            break;
        case 7:
            Add(id(x, y, 4), id(x, y, 1), 1, 1);
            Add(id(x, y, 4), id(x, y, 2), 1, 2);
            Add(id(x, y, 4), id(x, y, 3), 1, 1);
            break;
        case 11:
            Add(id(x, y, 3), id(x, y, 1), 1, 2);
            Add(id(x, y, 3), id(x, y, 2), 1, 1);
            Add(id(x, y, 3), id(x, y, 4), 1, 1);
            break;
        case 13:
            Add(id(x, y, 2), id(x, y, 1), 1, 1);
            Add(id(x, y, 2), id(x, y, 3), 1, 1);
            Add(id(x, y, 2), id(x, y, 4), 1, 2);
            break;
        case 14:
            Add(id(x, y, 1), id(x, y, 2), 1, 1);
            Add(id(x, y, 1), id(x, y, 3), 1, 2);
            Add(id(x, y, 1), id(x, y, 4), 1, 1);
            break;
        }
    }
}

signed main()
{
    n = read(), m = read();
    s = 0, t = _ - 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            int p = read();
            build(i, j, p);
        }
    dinic();
    write(maxflow * 2 == sum ? mincost : -1);
    return 0;
}