BZOJ 2668 - [cqoi2012]交换棋子

#图论 #思维 #网络流 #费用流

Published on 2017-01-11

题目地址

描述

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

请你输出最小交换总次数，无解输出 -1。

分析

首先判掉起始状态和目标状态黑色棋子不等的情况（无解），下面默认两种状态黑色棋子相等。

我们可以发现，交换两个同色棋子是毫无意义的，交换两个异色格子，相当于把黑色格子移动了一步。所以我们这个题可以转化为这样一个模型：

给定一些黑色棋子的初始位置，再给定一些目标位置，你每次可以将一个黑色棋子向相邻的格子移动，在满足限制的情况下，如何移动才能使得所有终止位置上都有一个黑色棋子且移动次数最少？

我们需要知道一个事实，给出任意一个移动方案，都可以调整移动顺序使得移动的过程中棋子不会重叠，所以我们可以认为每个棋子的移动是独立的。所以这个模型可以转化为费用流：建立源点汇点，将每个格子看做一个点。考虑所有格子，如果初始和目标状态的棋子颜色相同，就不考虑它。如果初始为黑（意味着目标为白），从源点向这个格子连边；如果初始为白（意味着目标为黑），从这个格子连边向汇点连边。

然后就是相邻的格子直接连边，费用设置为 $1$ 。重要的是如何用流量表示限制，将一个格子代表的点拆为 2 个（一个负责连入边，一个负责连出边），我们考虑拆出的两个点之间的流量限制 $c$ 。对于这个格子，题目限制的是「参与交换的次数 $m_{i, j}$ 」，而我们这个拆的这两个点之间的流量代表的是「经过的次数」。由于一次交换有两个点参与，所以这个流量不能 $c$ 简单的设置为 $m_{i, j}$ ，需要分析性质。

我们考虑如何用交换实现黑棋子的移动：，相邻两个格子都要交换一次。其中 $v_1$ 和 $v_k$ 只被交换了 $1$ 次，其余的都被交换了 $2$ 次。

也就是说，如果一个格子作为起点或者终点（就是向源点或者汇点连了边），它会被交换奇数次，否则它被交换偶数次。考虑「参与交换的次数」与「经过的次数」之间的关系，对于非起点非终点的格子，「参与交换的次数」= 2 *「经过的次数」，所以只需要将这种点限制经过 $\lfloor \frac {m_{i, j}} 2\rfloor$ 次。对于起点或者终点，「参与交换的次数」 = 2 *「经过的次数」 - 1，所以只需要将这种点限制经过 $\lfloor \frac {m_{i, j}} 2 + 1\rfloor$ 次即可。

跑最小费用流，满流则有解，否则无解。由于一次移动对应一次交换，所以最小费用即为最小交换次数。

代码

//  Created by Sengxian on 2016/12/29.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2668 费用流
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 20 + 3, MAX_M = 20 + 3, INF = 0x3f3f3f3f;

namespace MinCostMaxFlow {
    const int MAX_NODE = MAX_N * MAX_M * 2 + 2;
    struct edge {
        int to, cost, cap, rev;
        edge(int to, int cost, int cap, int rev): to(to), cost(cost), cap(cap), rev(rev) {}
    };
    vector<edge> G[MAX_NODE];

    inline void addEdge(int f, int t, int cap, int cost) {
        G[f].push_back(edge(t, cost, cap, G[t].size()));
        G[t].push_back(edge(f, -cost, 0, G[f].size() - 1));
    }

    int dis[MAX_NODE], preve[MAX_NODE], prevv[MAX_NODE];
    bool inq[MAX_NODE];

    int minCostMaxFlow(int s, int t, int flow) {
        int ans = 0;
        while (flow) {
            queue<int> q;
            memset(dis, 0x3f, sizeof dis);
            memset(inq, 0, sizeof inq);
            q.push(s), dis[s] = 0;

            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                for (int i = 0; i < (int)G[u].size(); ++i) {
                    edge &e = G[u][i];
                    if (e.cap && e.cost + dis[u] < dis[e.to]) {
                        dis[e.to] = dis[u] + e.cost;
                        prevv[e.to] = u, preve[e.to] = i;
                        if (!inq[e.to]) q.push(e.to), inq[e.to] = true;
                    }
                }
            }
            if (dis[t] == INF) return -1;

            int d = flow;
            for (int u = t; u != s; u = prevv[u]) d = min(d, G[prevv[u]][preve[u]].cap);
            ans += d * dis[t], flow -= d;

            for (int u = t; u != s; u = prevv[u]) {
                edge &e = G[prevv[u]][preve[u]];
                e.cap -= d;
                G[e.to][e.rev].cap += d;
            }
        }
        return ans;
    }
}

using namespace MinCostMaxFlow;

int n, m;
char A[MAX_N][MAX_N], B[MAX_N][MAX_M], C[MAX_N][MAX_M];

#define ID(i, j) ((i) * m + (j))

inline bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), m = readInt();
    for (int i = 0; i < n; ++i) scanf("%s", A[i]);
    for (int i = 0; i < n; ++i) scanf("%s", B[i]);
    for (int i = 0; i < n; ++i) scanf("%s", C[i]);

    int S = n * m * 2, T = n * m * 2 + 1, c = 0, cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (A[i][j] == '1') ++c;
            if (B[i][j] == '1') --c;
            if (A[i][j] == B[i][j]) addEdge(ID(i, j) * 2, ID(i, j) * 2 + 1, (C[i][j] - '0') / 2, 0);
            else addEdge(ID(i, j) * 2, ID(i, j) * 2 + 1, (C[i][j] - '0' + 1) / 2, 0);
            for (int k = 0; k < 8; ++k) {
                static const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1}, dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
                int x = i + dx[k], y = j + dy[k];
                if (check(x, y)) addEdge(ID(i, j) * 2 + 1, ID(x, y) * 2, INF, 1);
            }
        }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (A[i][j] == '1' && B[i][j] == '0') addEdge(S, ID(i, j) * 2, 1, 0), ++cnt;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (B[i][j] == '1' && A[i][j] == '0') addEdge(ID(i, j) * 2 + 1, T, 1, 0);

    if (c != 0) puts("-1");
    else printf("%d\n", minCostMaxFlow(S, T, cnt));
    return 0;
}

Codeforces 757F - Team Rocket Rises Again BZOJ 4408 - [Fjoi 2016]神秘数

Sengxian's Blog

BZOJ 2668 - [cqoi2012]交换棋子

描述

分析

代码