luoguP4003 无限之环

网络流建图

无限之环

思路

典型的网络流，难点在建图（我改了三次建图方法），以下简述，可以对照代码理解：

将格子编号为 $id[x, y]$ ，将格子的四边编号为 $idm[x, y, 0/1/2/3]$ ，把格子黑白染色， $S$ 连向黑点，白点连向 $T$

分接头数讨论：

1. 接头数为 $0$ ，不管
2. 接头数为 $1$ ，直接建
3. 接头数为 $2$ ，建四个辅助点代表四个方向，记为 $tct[0 \sim 3]$ ，黑点就由 $id[x, y]$ 向不用旋转就可接上的辅助点连容量为 $1$ 的边，再从不用旋转就可接上的辅助点向对面（上对下，左对右）连容量为 $1$ ，**代价为 $1$**的边（这就模拟了旋转），最后辅助点向对应的 $idm$ 连边；白点同理
4. 接头数为 $3$ ，类似于为 $2$ ，只是代价设计不同
5. 接头数为 $4$ ，直接连

代码

#include <bits/stdc++.h>
const int N = 2000 + 100, INF = 0x3f3f3f3f;
int n, m, S, T, a[N][N];
struct Edge{ int ne, ver, w, c; } e[N * N];
int h[N * 15], idx = 0;
int ct = 0, id[N][N], idm[N][N][4], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
int mnc, mxf, cur[N * 15], dis[N * 15], goal = 0, tct[4];
bool vis[N * 15];
void add(int x, int y, int z, int c){ e[idx] = {h[x], y, z, c}, h[x] = idx++; }
void dad(int x, int y, int z, int c){ add(x, y, z, c), add(y, x, 0, -c); }
void tb1(int x, int y, int t[4]) //tb:to_build,下同
{
    //1就不必建辅助点了
    if ((x + y) & 1)
    {
        dad(S, id[x][y], 1, 0);
        for (int i = 0; i <= 3; ++i) t[i] ^= 1;
        for (int i = 0; i <= 3; ++i) if (!t[i]){ t[i ^ 1] = 2; break; }
        for (int i = 0; i <= 3; ++i) dad(id[x][y], idm[x][y][i], 1, t[i]);
    }
    else
    {
        for (int i = 0; i <= 3; ++i) t[i] ^= 1;
        for (int i = 0; i <= 3; ++i) if (!t[i]){ t[i ^ 1] = 2; break; }
        for (int i = 0; i <= 3; ++i) dad(idm[x][y][i], id[x][y], 1, t[i]);
        dad(id[x][y], T, 1, 0);
    }
}
void tb2(int x, int y, int t[4])
{
    if ((x + y) & 1)
    {
        dad(S, id[x][y], 2, 0);
        if (t[0] == t[1]) //直线直接建
        {
            for (int i = 0; i <= 3; ++i) if (t[i]) dad(id[x][y], idm[x][y][i], 1, 0); 
        }
        else
        {
            for (int i = 0; i <= 3; ++i) tct[i] = ++ct; //辅助点
            for (int i = 0; i <= 3; ++i) if (t[i]) dad(id[x][y], tct[i], 1, 0), dad(tct[i], tct[i ^ 1], 1, 1);
            for (int i = 0; i <= 3; ++i) dad(tct[i], idm[x][y][i], 1, 0);
        }
    }
    else 
    {
        if (t[0] == t[1])
        {
            for (int i = 0; i <= 3; ++i) if (t[i]) dad(idm[x][y][i], id[x][y], 1, 0); 
        }
        else
        {
            for (int i = 0; i <= 3; ++i) tct[i] = ++ct;
            for (int i = 0; i <= 3; ++i) if (t[i]) dad(tct[i], id[x][y], 1, 0), dad(tct[i ^ 1], tct[i], 1, 1);
            for (int i = 0; i <= 3; ++i) dad(idm[x][y][i], tct[i], 1, 0);
        }
        dad(id[x][y], T, 2, 0);
    }
}
void tb3(int x, int y, int t[4])
{
    int where;
    for (int i = 0; i <= 3; ++i) tct[i] = ++ct;
    if ((x + y) & 1)
    {
        dad(S, id[x][y], 3, 0);
        for (int i = 0; i <= 3; ++i) if (t[i]) dad(id[x][y], tct[i], 1, 0);
        for (int i = 0; i <= 3; ++i) if (!t[i]){ t[i ^ 1] = 2, where = i; break; }
        for (int i = 0; i <= 3; ++i) if (t[i]) dad(tct[i], tct[where], 1, t[i]);
        for (int i = 0; i <= 3; ++i) dad(tct[i], idm[x][y][i], 1, 0);
    }
    else
    {
        for (int i = 0; i <= 3; ++i) if (t[i]) dad(tct[i], id[x][y], 1, 0);
        for (int i = 0; i <= 3; ++i) if (!t[i]){ t[i ^ 1] = 2, where = i; break; }
        for (int i = 0; i <= 3; ++i) if (t[i]) dad(tct[where], tct[i], 1, t[i]);
        for (int i = 0; i <= 3; ++i) dad(idm[x][y][i], tct[i], 1, 0);
        dad(id[x][y], T, 3, 0);
    }
}
void tb4(int x, int y)
{
    if ((x + y) & 1)
    {
        dad(S, id[x][y], 4, 0);
        for (int i = 0; i <= 3; ++i) dad(id[x][y], idm[x][y][i], 1, 0);
    }
    else
    {
        for (int i = 0; i <= 3; ++i) dad(idm[x][y][i], id[x][y], 1, 0);
        dad(id[x][y], T, 4, 0);
    }
}
void build() //为了方便,把右和下换一下,即上下右左
{
    memset(h, -1, sizeof h);
    int t[4], s;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) id[i][j] = ++ct;
    for (int i = 1; i <= n + 1; ++i)
        for (int j = 1; j <= m + 1; ++j)
        {
            idm[i][j][0] = idm[i - 1][j][1] = ++ct;
            idm[i][j][3] = idm[i][j - 1][2] = ++ct;
        }
    S = ++ct, T = ++ct;
    int gs = 0, gt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1, k, ta; j <= m; ++j)
        {
            for (k = s = 0, ta = a[i][j]; k <= 3; ++k) s += (t[k] = ((ta >> k) & 1));
            std::swap(t[1], t[2]); 
            if (s == 1) tb1(i, j, t);
            else if (s == 2) tb2(i, j, t);
            else if (s == 3) tb3(i, j, t);
            else if (s == 4) tb4(i, j);
            if ((i + j) & 1) gs += s; //奇数为出点,偶数为入点
            else gt += s;
        }
    goal = std::max(gs, gt); //不这样的话1*1的图要挂
}
bool spfa()
{
    memset(dis, 0x3f, sizeof dis);
    memcpy(cur, h, sizeof h);
    std::queue<int> q;
    for (q.push(S), dis[S] = 0, vis[S] = true; !q.empty(); )
    {
        int x = q.front(); q.pop();
        vis[x] = false;
        for (int i = h[x], y; ~i; i = e[i].ne) if (dis[y = e[i].ver] > dis[x] + e[i].c && e[i].w)
        {
            dis[y] = dis[x] + e[i].c;
            if (!vis[y]) vis[y] = true, q.push(y);
        }
    }
    return dis[T] != INF;
}
int find(int x, int lim)
{
    if (x == T) return lim;
    vis[x] = true;
    int flow = 0, y, t;
    for (int i = cur[x]; ~i && flow < lim; i = e[i].ne)
    {
        cur[x] = i;
        if (!vis[y = e[i].ver] && dis[y] == dis[x] + e[i].c && e[i].w)
        {
            t = find(y, std::min(lim - flow, e[i].w));
            e[i].w -= t, e[i ^ 1].w += t, flow += t, mnc += t * e[i].c;
        }
    }
    vis[x] = false;
    return flow;
}
void mcmf()
{
    mnc = mxf = 0;
    int flow;
    while (spfa()) while ((flow = find(S, INF))) mxf += flow; 
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
    build(), mcmf();
    if (mxf < goal) puts("-1");
    else printf("%d\n", mnc);
    return 0;
}