2016北京集训测试赛（六）Problem B: 矩阵

Solution

最小割.

参考BZOJ 3144切糕

在那道题的基础上将建图方法稍作变形: 我们对格子进行黑白染色, 对于两个格子之和\(\le k\)的限制, 就可以确定其中一个是白色格子, 一个是黑色格子. 我们让黑色格子和白色格子的点的顺序相反, 就可以表示限制了.

目前的代码还是WA的.

#include <cstdio>

#include <cctype>

#include <vector>

#include <deque>

#include <algorithm>

namespace Zeonfai

{

    inline int getInt()

    {

        int a = 0, sgn = 1;

        char c;

        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

const int N = 50, M = 50, INF = (int)1e9;

int D[N][M], R[N][M];

struct graph

{

    struct node;

    struct edge

    {

        node *v; int cap; edge *op;

    };

    struct node

    {

        std::vector<edge*> edg;

        int dep;

        inline node()

        {

            edg.clear();

        }

    }nd[N][M][11], *S, *T;

    inline graph()

    {

        S = new node; T = new node;

    }

    inline void addEdge(node *u, node *v, int cap)

    {

        edge *a = new edge, *b = new edge;

        a->v = v; a->cap = cap; a->op = b;

        b->v = u; b->cap = 0; b->op = a;

        u->edg.push_back(a); v->edg.push_back(b);

    }

    int cnt;

    void clear(node *u)

    {

        u->dep = - cnt;

        for(auto edg : u->edg) if(edg->v->dep != -cnt) clear(edg->v);

    }

    inline int BFS()

    {

        ++ cnt; clear(S); S->dep = 0;

        static std::deque<node*> que; que.clear();

        que.push_back(S);

        for(; ! que.empty(); que.pop_front())

        {

            node *u = que.front();

            for(auto edg : u->edg) if(edg->cap && edg->v->dep == - cnt) edg->v->dep = u->dep + 1, que.push_back(edg->v);

        }

        return T->dep != - cnt;

    }

    int DFS(node *u, int flw)

    {

        if(u == T) return flw;

        int flowSum = 0;

        for(auto edg : u->edg) if(edg->cap && edg->v->dep == u->dep + 1)

        {

            int currentFlow = DFS(edg->v, std::min(edg->cap, flw - flowSum));

            flowSum += currentFlow;

            edg->cap -= currentFlow; edg->op->cap += currentFlow;

            if(flowSum == flw) return flowSum;

        }

        if(! flowSum) u->dep = -1;

        return flowSum;

    }

    inline int dinic()

    {

        cnt = 0;

        int res = 0;

        while(BFS())

            res += DFS(S, INF);

        return res;

    }

}G;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("matrix.in", "r", stdin);

    freopen("matrix.out", "w", stdout);

    #endif

    using namespace Zeonfai;

    int n = getInt(), m = getInt();

    for(int i = 0; i < n - 1; ++ i) for(int j = 0; j < m; ++ j) D[i][j] = getInt();

    for(int i = 0; i < n; ++ i) for(int j = 0; j < m - 1; ++ j) R[i][j] = getInt();

    for(int i = 0; i < n; ++ i) for(int j = 0; j < m; ++ j)

    {

        if(i ^ j & 1)

        {

            G.addEdge(G.S, &G.nd[i][j][9], INF);

            for(int k = 9; k >= 1; -- k) G.addEdge(&G.nd[i][j][k], &G.nd[i][j][k - 1], 10 - k);

            G.addEdge(&G.nd[i][j][0], G.T, INF);

            for(int k = 0; k <= 9; ++ k)

            {

                if(i + 1 < n && D[i][j] - k <= 10 && D[i][j] - k >= 1) G.addEdge(&G.nd[i + 1][j][D[i][j] - k], &G.nd[i][j][k], INF);

                if(j + 1 < m && R[i][j] - k <= 10 && R[i][j] - k >= 1) G.addEdge(&G.nd[i][j + 1][R[i][j] - k], &G.nd[i][j][k], INF);

            }

        }

        else

        {

            G.addEdge(G.S, &G.nd[i][j][1], INF);

            for(int k = 1; k <= 9; ++ k) G.addEdge(&G.nd[i][j][k], &G.nd[i][j][k + 1], 10 - k);

            G.addEdge(&G.nd[i][j][10], G.T, INF);

            for(int k = 1; k <= 10; ++ k)

            {

                if(i + 1 < n && D[i][j] - k <= 9 && D[i][j] - k >= 0) G.addEdge(&G.nd[i][j][k], &G.nd[i + 1][j][D[i][j] - k], INF);

                if(j + 1 < m && R[i][j] - k <= 9 && R[i][j] - k >= 0) G.addEdge(&G.nd[i][j][k], &G.nd[i][j + 1][R[i][j] - k], INF);

            }

        }

    }

    printf("%d\n", n * m * 10 - G.dinic());

}