神奇的建模。。。原题链接

如果你真的把交换看成交换,就\(GG\)了。首先我们要把交换看成是白棋的移动。

然后,很容易的就想到建模的大致思路:建立超级源点S和超级汇点T,从S向初始局面每个白棋所在的格子连边,从目标局面每个白棋所在的格子向T连边,在相邻的格子中间加一些有限制的边,跑一波费用流。

那中间的那些边应该怎么加呢,先考虑把每个格子拆成两个点,中间连一条以交换次数为流量上限的边。但是这样会有问题,考虑某个白棋移动路径上的点,其实只有开头的格子交换了一次,中间的都是两次。只拆两个体现不了在中间或首尾的差别,那我们就拆三个。

把一个格子拆成三个点:TYPE1TYPE2TYPE3,分别表示流入,当前格子,流出。与ST的连边改为向TYPE2连边,与相邻格子的连边在TYPE1TYPE3之间连,另外从TYPE2TYPE1TYPE3连边,这样就能体现在路径上位置的差别了。

那这些边的容量和费用该怎么设置呢?

1.TYPE1TYPE3之间的连边容量为\(INF\),费用为\(1\)。

2.STYPE2TYPE2T容量为\(1\),费用为\(0\)。

3.TYPE2TYPE1TYPE3的连边(重点):

对于某个格子(假设它的交换上限为\(w\),"/"号代表整除):

①若初始为白棋,目标为黑棋,则从TYPE1TYPE2连一条容量为\(w/2\),费用为\(0\)的边,从TYPE2TYPE3连一条容量为\((w+1)/2\),费用为\(0\)的边

②若初始为黑棋,目标为白棋,则从TYPE1TYPE2连一条容量为\((w+1)/2\),费用为\(0\)的边,从TYPE2TYPE3连一条容量为\(w/2\),费用为\(0\)的边

③若始末颜色相同,则从TYPE1TYPE2连一条容量为\(w/2\),费用为\(0\)的边,从TYPE2TYPE3连一条容量为\(w/2\),费用为\(0\)的边

为什么权值要这样设,因为我们要保持收支平衡,使得每个格子在交换之后的颜色是对的。还有我们考虑的是白棋的移动,因此①应该会多一次流出,于是我们尽量把零头分给TYPE2TYPE3之间的那条边。②同理。

注意判\(-1\)!

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define N 10000
#define INF 0x3f3f3f3f int n, m, S, T; struct MCMF
{
struct Edge
{
int from, to, cap, flow, cost;
};
int S, T;
int d[N+5], a[N+5], vis[N+5], pre[N+5];
vector<int> G[N+5];
vector<Edge> edges;
void init(int S, int T)
{
this->S = S, this->T = T;
}
void addEdge(int from, int to, int cap, int cost)
{
edges.pb(Edge{from, to, cap, 0, cost}), edges.pb(Edge{to, from, 0, 0, -cost});
G[from].pb(edges.size()-2), G[to].pb(edges.size()-1);
}
int SPFA(int &flow, int &cost)
{
memset(d, 0x3f, sizeof d), memset(vis, 0, sizeof vis);
d[S] = 0, a[S] = INF, vis[S] = 1, pre[S] = 0;
queue<int> q;
q.push(S);
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = 0; i < G[u].size(); ++i)
{
Edge &e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u]+e.cost)
{
d[e.to] = d[u]+e.cost;
pre[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap-e.flow);
if(!vis[e.to]) vis[e.to] = 1, q.push(e.to);
}
}
}
if(d[T] == INF) return 0;
int u = T;
flow += a[T], cost += d[T]*a[T];
while(u != S)
{
edges[pre[u]].flow += a[T], edges[pre[u]^1].flow -= a[T];
u = edges[pre[u]].from;
}
return 1;
}
pii minCost()
{
int flow = 0, cost = 0;
while(SPFA(flow, cost));
return mp(flow, cost);
}
}solver; int Val(char c)
{
return c-'0';
} int TYPE1(int i, int j)
{
return ((i-1)*m+j)*3-2;
} int TYPE2(int i, int j)
{
return ((i-1)*m+j)*3-1;
} int TYPE3(int i, int j)
{
return ((i-1)*m+j)*3;
} int a[25][25], b[25][25], w[25][25];
int d[8][2] = {-1,0,1,0,0,-1,0,1,-1,-1,-1,1,1,-1,1,1};
//0:black 1:white
int main()
{
scanf("%d%d", &n, &m);
S = 0, T = 3*n*m+1;
solver.init(S, T);
char c;
int sum = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, a[i][j] = Val(c), sum += a[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, b[i][j] = Val(c);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, w[i][j] = Val(c);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(a[i][j]) solver.addEdge(S, TYPE2(i, j), 1, 0);
if(b[i][j]) solver.addEdge(TYPE2(i, j), T, 1, 0);
if(a[i][j] == 0 && b[i][j] == 1)
solver.addEdge(TYPE1(i, j), TYPE2(i, j), (w[i][j]+1)/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), w[i][j]/2, 0);
else if(a[i][j] == 1 && b[i][j] == 0)
solver.addEdge(TYPE1(i, j), TYPE2(i, j), w[i][j]/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), (w[i][j]+1)/2, 0);
else
solver.addEdge(TYPE1(i, j), TYPE2(i, j), w[i][j]/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), w[i][j]/2, 0);
for(int k = 0, ti, tj; k < 8; ++k)
{
ti = i+d[k][0], tj = j+d[k][1];
if(ti < 1 || ti > n || tj < 1 || tj > m) continue;
solver.addEdge(TYPE3(i, j), TYPE1(ti, tj), INF, 1);
}
}
pii res = solver.minCost();
if(res.first != sum) printf("-1\n");
else printf("%d\n", res.second);
return 0;
}
05-11 14:10