BZOJ 2668 CQOI 2012 交換棋子 費用流

BZOJ 2668 CQOI 2012 交換棋子 費用流

題目大意

給出一個網格圖，每個格子上有移動次數限制。每次可以交換相鄰的兩個棋子（有公共點就算相鄰）。給出一個初始狀態，問最少需要多少步達到目標狀態。

思路

這個題主要是限制是每個格子，而不是棋子。我們對每個格子拆點，相鄰的格子之間連邊，經過一個格子的時候的費用是2，流量是（正常的流量+這個點是入點+這個點是出點）/2，在連S和T的時候要將費用設成-1。這樣跑出來的最小費用的一半就是答案。
注意要特判一下起始情況和目標情況黑子不同的情況。。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 
#include 
#define MAXE 1000010
#define MAXP 1010
#define MAX 50
#define S 0
#define T (MAXP - 1)
#define INF 0x3f3f3f3f
using namespace std;
const int dx[9] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
const int dy[9] = {0, -1, 0, 1, -1, 1, -1, 0, 1};

int blacks, _blacks;

struct MinCostMaxFlow{
    int head[MAXP], total;
    int _next[MAXE], aim[MAXE], flow[MAXE], cost[MAXE];
    int f[MAXP], from[MAXP], p[MAXP];
    bool v[MAXP];

    MinCostMaxFlow():total(1) {}
    void Add(int x, int y, int f, int c) {
        _next[++total] = head[x];
        aim[total] = y;
        flow[total] = f;
        cost[total] = c;
        head[x] = total;
    }
    void Insert(int x, int y, int f, int c) {
        Add(x, y, f, c);
        Add(y, x, 0, -c);
    }
    bool SPFA() {
        static queue q;
        while(!q.empty())   q.pop();
        memset(f, 0x3f, sizeof(f));
        memset(v, false, sizeof(v));
        f[S] = 0;
        q.push(S);
        while(!q.empty()) {
            int x = q.front(); q.pop();
            v[x] = false;
            for(int i = head[x]; i; i = _next[i])
            if(flow[i] && f[aim[i]] > f[x] + cost[i]) {
                f[aim[i]] = f[x] + cost[i];
                if(!v[aim[i]])
                    v[aim[i]] = true, q.push(aim[i]);
                from[aim[i]] = x;
                p[aim[i]] = i;
            }
        }
        return f[T] != INF;
    }
    int EdmondsKarp() {
        int re = 0, total_flow = 0;
        while(SPFA()) {
            int max_flow = INF;
            for(int i = T; i != S; i = from[i])
                max_flow = min(max_flow, flow[p[i]]);
            for(int i = T; i != S; i = from[i]) {
                flow[p[i]] -= max_flow;
                flow[p[i] ^ 1] += max_flow;
            }
            re += f[T] * max_flow;
            total_flow += max_flow;
        }
        return total_flow == blacks ? (re >> 1) : -1;
    }
}solver;

int m, n;
char s[MAX][MAX];
bool _in[MAX][MAX], _out[MAX][MAX];
int src[MAX][MAX];
int num[MAX][MAX], cnt;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; ++i) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= n; ++j) {
            _in[i][j] = s[i][j] == '1';
            blacks += _in[i][j];
        }
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= n; ++j) {
            _out[i][j] = s[i][j] == '1';
            _blacks += _out[i][j];
        }
    }
    if(blacks != _blacks) {
        puts("-1");
        return 0;
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= n; ++j)
            src[i][j] = s[i][j] - '0';
    }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            num[i][j] = ++cnt;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j) {
            if(_in[i][j])
                solver.Insert(S, num[i][j] << 1, 1, -1);
            if(_out[i][j])
                solver.Insert(num[i][j] << 1|1, T, 1, -1);
            solver.Insert(num[i][j] << 1, num[i][j] << 1|1, (src[i][j] + _in[i][j] + _out[i][j]) >> 1, 2);
            for(int k = 1; k <= 8; ++k) {
                int fx = i + dx[k], fy = j + dy[k];
                if(!fx || !fy || fx > m || fy > n)  continue;
                solver.Insert(num[i][j] << 1|1, num[fx][fy] << 1, INF, 0);
            }
        }
    cout << solver.EdmondsKarp() << endl;
    return 0;
}