题目大意
给出一个网格图，每个格子上有移动次数限制。每次可以交换相邻的两个棋子（有公共点就算相邻）。给出一个初始状态，问最少需要多少步达到目标状态。
思路
这个题主要是限制是每个格子，而不是棋子。我们对每个格子拆点，相邻的格子之间连边，经过一个格子的时候的费用是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; }