Description

有一个 \(n\) 行 \(m\) 列的黑白棋盘, 你每次可以交换两个相邻格子 (相邻是指有公共边或公共顶点) 中的棋子, 最终达到目标状态. 要求第 \(i\) 行第 \(j\) 列的格子只能参与 \(m_{i,j}\) 次交换.

Input

第一行包含两个整数 \(n, m (1 \leq n, m \leq 20)\). 以下 \(n\) 行为初始状态, 每行为一个包含 \(m\) 个字符的 0-1 串, 其中 0 表示黑色棋子, 1 表示白色棋子. 以下 \(n\) 行为 目标状态, 格式同初始状态. 以下 \(n\) 行每行为一个包含 \(m\) 个 0~ 9 数字的字符串, 表示 每个格子参与交换的次数上限.

Output

输出仅一行, 为最小交换总次数. 如果无解, 输出-1.

Sample Input

3 3
110
000
001
000
110
100
222
222
222

Sample Output

4

Solution

简单费用流拆点+双限制流量 (可能无法推广)+1A (SPFA 费用流一次写对好开心)

下面参考某位神犇的题解:http://blog.csdn.net/vmurder/article/details/44702813

首先图转化成源点往开始图的黑点 (当然你要用白点也不是不行) 流流量, 最终从结束图的黑点流向汇点. 这个应该都能想到.

然后关键是怎么在流过一次后同时限制两个点.

这也是我所想知道的……可是, 下面的方法并没有告诉我该如何实现它, 它用的是分析改流量. [请允许我做一个捂脸熊的表情]

我们分析:

如果一个点是初始图上的黑点, 那么它可以

最多可以流入 \(\lfloor \frac{限制修改次数}{2} \rfloor\), 最多可以流出 \(\lfloor \frac{限制修改次数+1}{2} \rfloor\)

如果一个点是目标图上的黑点, 那么它可以

最多可以流入 \(\lfloor \frac{限制修改次数+1}{2} \rfloor\), 最多可以流出 \(\lfloor \frac{限制修改次数}{2} \rfloor\)

否则

最多可以流入 \(\lfloor \frac{限制修改次数}{2} \rfloor\), 最多可以流出 \(\lfloor \frac{限制修改次数}{2} \rfloor\)

然后我们需要特判一下如果一个点既是初始图上的黑点, 又是目标图上上的黑点, 那么显然 它的流入流出都应该跟 否则那一部分一样. 因为流入流出以后跟正常的点一样了么.

然后费用什么乱搞就行了, 想设哪就设哪 (但是乱设的话最终答案可能需要/2)

注意是八连通.

还有另一位大神的题解:http://timeplayer.blog.163.com/blog/static/20371825420151292735677/

首先把每个点拆点, 然后把每个格子看成一个 “交换站”, 把初始图的 1 看成一个 “入”, 把目标图的 1 看成一个 “出”

那么问题就是流从入到出经过一些交换站, 使得交换站被经过的次数最少.

我们认为流不能在交换站停留, 所以流经过交换站一定是会付出代价 2: 交换进来一次, 交换出去一次.

然后注意有 “出” 或者 “入” 的点比较特殊, 因为这个点必然要经过自己的交换站一次, 而且这次经过是不需要代价的,

所以把每个位置拆成点 1 和 2, 连边 1->2 容量是: (可交换次数+[这个点是 “入”] +[这个点是 “出”] ) /2, 费用是 2.

如果这个点是入, 那么 S->1 容量是 1, 费用是-1

如果这个点是出, 那么 2->T 容量是 1, 费用是-1

最后注意判一下无解, 问题解决.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1500, maxm = 10010, maxn_2 = 25;
const int infinit = 0x003f3f3f;

const int move_x[8] = {  1,  0, -1, -1, -1,  0,  1,  1 },
          move_y[8] = {  1,  1,  1,  0, -1, -1, -1,  0 };

class SpfaMaxFlow
{
public:
    struct edge
    {
        int u, v, flow, cost;
        edge *next, *rev;
    };
    edge *edges[maxn], *from[maxn], epool[maxm];
    int n, s, t, ecnt;
    void add_edge(int u, int v, int flow, int cost)
    {
        // printf("add edge %d %d %d %d\n", u, v, flow, cost);
        // printf("add edge %d %d %d %d\n", v, u, 0, -cost);
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    int dist[maxn];
    bool inque[maxn];
    bool bfs_spfa(void)
    {
        queue<int> que;
        for (int i = 0; i <= n; i++)
            inque[i] = false, dist[i] = infinit, from[i] = NULL;
        que.push(s);
        inque[s] = true, dist[s] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        if (dist[t] < infinit)
            return true;
        return false;
    }
    int max_flow;
    int min_cost;
    void eval(void)
    {
        int tmp = 0;
        while (bfs_spfa()) {
            // Currently calculating tmp = maximum flow on graph
            tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            // Applying flow to removal operations...
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= tmp,
                ep->rev->flow += tmp;
            // Evaluating cost...
            max_flow += tmp;
            min_cost += tmp * dist[t];
        }
        return ;
    }
} graph;

int read_number(void) { char ch = '\0';
    while (ch < '0' || ch > '9') ch = getchar();
    return ch - '0'; }

int n, m;
int begn[maxn_2][maxn_2], term[maxn_2][maxn_2]; // The two states of chess pieces
int id[maxn_2][maxn_2], id_cnt; // id[i][j] = n*(i-1)+j

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            id[i][j] = ++id_cnt, id_cnt++, id_cnt++;
    // Reading more data and building graph
    graph.n = n*m*3 + 2;
    graph.s = 0;
    graph.t = n*m*3 + 1;
    int dup_count = 0; // Check if two states' chess pieces' count doesn't match
    int pnt_count = 0;
    // Given commence state
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            begn[i][j] = read_number();
            if (begn[i][j] > 0) {
                graph.add_edge(graph.s, id[i][j] + 1, 1, 0);
                dup_count++;
            }
        }
    pnt_count = dup_count; // Copy data for preservation
    // Required termination state
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            term[i][j] = read_number();
            if (term[i][j] > 0) {
                graph.add_edge(id[i][j] + 1, graph.t, 1, 0);
                dup_count--;
            }
        }
    // If it was not meant to be possible, leave it
    if (dup_count != 0) {
        // Impossible because the count doesn't match
        printf("-1\n");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int flow, flow_a, flow_b;
            flow = read_number();
            if (!flow) continue;
            flow_a = begn[i][j] ? (flow + 1) / 2 : flow / 2;
            flow_b = term[i][j] ? (flow + 1) / 2 : flow / 2;
            if (begn[i][j] && term[i][j])
                flow_a = flow_b = flow / 2;
            // Adding into graph
            graph.add_edge(id[i][j], id[i][j] + 1, flow_b, 1);
            graph.add_edge(id[i][j] + 1, id[i][j] + 2, flow_a, 1);
        }
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 8; k++) {
                int x = i + move_x[k],
                    y = j + move_y[k];
                if (id[x][y])
                    graph.add_edge(id[i][j] + 2, id[x][y], infinit, 0);
            }
    }
    // Evaluating max-flow-min-cost model
    graph.eval();
    if (graph.max_flow < pnt_count) {
        // Unable to satisfy delimitations
        printf("-1");
        return 0;
    }
    printf("%d\n", graph.min_cost / 2);
    return 0;
}