P3159 [CQOI2012]交换棋子

洛谷P3159.
分析:
1:把白棋看作空的位置,那么只需要 移动黑棋子就行了. 在一个黑棋的移动路径中,除了第一个位置和最后一个位置,其余位置都是小号 两次交换次数. 因为一次从其他地方走到当前,一次从当前再走出去.共两次.

​2: 如果当前点起始和终止都有棋子,那么相当于这个位置没有棋子. 因为考虑这个点的棋子不移动,那么其他棋子的移动都要绕着这个棋子过.显然这个棋子相当于没有移动过, 也就不需要考虑. 再如果, 别的棋子需要移到当前的棋子,而当前的棋子最终要落在其他的坐标上,那么就相当于其他的棋子踩在这个棋子的头上过去了,因为整个变化的路线完全一致.

那么这里的做法就是把一个坐标点拆成3个点,即 in, mid, out,in到mid连线表示是从其他点走到当前的, 从mid到out连线 表示是从当前到外面的其他坐标的移动. 而权值显然应该围绕该点的总的改变次数赋值. 但是赋值怎么 进行呢? 考虑到一个点进来和出去的次数差值不会超过1, 所以如果最大的允许改变次数是偶数可以 两个边权值都一样,不会出现问题,那么问题就是如果某一个点的最大允许的改变次数是奇数,那么被两个边分,就会多出1权值,这个1的分配是比较讲究的.这么想:

这里画了两个点之间拆点完之后的连线图, 其他更多的点都用同理来造图

如果当前的奇数值的点在起点处有棋子,那么如果终点处没有棋子,很明显,出来的交换次数要多1,那么把这个1赋值给mid 到 out的连边

如果当前的奇数值的点在起点处有棋子,那么如果终点处也有棋子,根据上面的分析2,相当于这个点没有棋子存在,那么即使有路径通过这里,进来和出来的次数一定一样,所以这个1无论给那一条边都没有关系

如果当前的奇数值的点在起点处没有棋子,那么如果终点处也没有棋子,那么同上:即使有路径通过这里,进来和出来的次数一定一样,所以这个1无论给那一条边都没有关系.

如果当前的奇数值的点在起点处没有棋子,那么如果终点处有棋子,那么很明显,进来的次数要多1,那么把这个1加给in 到mid 的连边.

那么拆点到这里就算完成了.

以上所有,费用全部为0

那么点之间怎么连接呢? 题中说了,一个点有八个方向都可以连通,那么如果两个点可以连通, 把对应的out连到另一个点的in点中就可以,费用为1.(因为我们需要用费用类比交换次数,所以一次的点之间的交换就是1个费用)

再之后,源点连接初始有棋子的坐标点,连接mid. 终止状态有棋子的坐标点的mid与汇点连接.费用为0, 流量为1.

那么如果我没有说落了什么的话造图就到这里全部结束.

那么我们分析这个图怎么用: 因为源点S连的是初始有棋子的坐标, 并且容量为1,那么我们可以看作一个棋子的转移路径就是一个流量,所以最大流和棋子数一致,说明可以顺利完成题目中的棋子移动.而费用就是转移的次数,因为我们的1费用设给了点之间转移的边, 所以是可以对应上的.

总之,题中所求的最小交换次数就是费用.

那么无解的情况就是一个流量与数据中棋子的数量不一致,或者数据中起始的棋子数和终止的棋子数不同,那么输出-1.

#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 60;const int maxm = 2e5 + 60;typedef long long ll;struct edge{int s, d, next;ll cap, cost;};struct graph{edge saveedges[maxm];int savecnt = 0;int head[maxn] = {0};void init(){savecnt = 0;memset(head, -1, sizeof(head));}//费用流必须双路,void adde(int s, int d, ll cap, ll cost){saveedges[savecnt].s = s;saveedges[savecnt].d = d;saveedges[savecnt].next = head[s];saveedges[savecnt].cap = cap;saveedges[savecnt].cost = cost;head[s] = savecnt++;swap(s, d);saveedges[savecnt].s = s;saveedges[savecnt].d = d;saveedges[savecnt].next = head[s];saveedges[savecnt].cap = 0;saveedges[savecnt].cost = -cost;head[s] = savecnt++;}} G;int cnt1 = 0;struct costflow{private://这两个图的信息edge *save_edge;int *head;int preeid[maxn]; //记录最短路中前驱边的编号//在最短路算法中自动更新,不用管bool inq[maxn];ll cost[maxn], flow[maxn];//查询费用最小的路inline bool SPFA(int s, int t){queue<int> q;memset(cost, 0x7f, sizeof(cost));memset(flow, 0x7f, sizeof(flow));memset(inq, 0, sizeof(inq));preeid[s] = -1;preeid[t] = -1;q.push(s);inq[s] = 1;cost[s] = 0;while (!q.empty()){int nowid = q.front();q.pop();inq[nowid] = 0;for (int eid = head[nowid]; eid != -1; eid = save_edge[eid].next){int d = save_edge[eid].d;if (save_edge[eid].cap && save_edge[eid].cost + cost[nowid] < cost[d]){cost[d] = save_edge[eid].cost + cost[nowid];flow[d] = min(flow[nowid], save_edge[eid].cap); //通过这条边能够给目标点多少流量preeid[d] = eid;                                //记录便宜的目标点if (inq[d] == 0){q.push(d);inq[d] = 1;}}}}//返回是否能够到达终点if (preeid[t] != -1)return 1;return 0;}public:inline void init(graph &g){save_edge = g.saveedges;head = g.head;}inline void maxflow(int s, int t){ll flow_res = 0;ll mincost = 0;while (SPFA(s, t)){flow_res += flow[t];mincost += cost[t] * flow[t];for (int patheid = preeid[t]; patheid != -1; patheid = preeid[save_edge[patheid].s]){save_edge[patheid].cap -= flow[t];save_edge[patheid ^ 1].cap += flow[t];}}if(flow_res!=cnt1){cout << -1 << endl;return;}printf(\"%lld\\n\", mincost);return;}} FLOW;#define id(i, j) m *(i - 1) + jint change[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};char start[26][26];char dest[26][26];char savem[26][26];int n, m;int main(){// freopen(\"in.txt\", \"r\", stdin);G.init();cin >> n >> m;int S = 0;int B = n * m;int T = B * 3 + 1;for (int i = 1; i <= n;i++){scanf(\"%s\", start[i] + 1);}for (int i = 1; i <= n;i++){scanf(\"%s\", dest[i] + 1);}for (int i = 1; i <= n;i++){scanf(\"%s\", savem[i] + 1);}for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){savem[i][j] -= \'0\';start[i][j] -= \'0\';dest[i][j] -= \'0\';if(savem[i][j]%2==0){G.adde(id(i, j), id(i, j) + B, savem[i][j] / 2, 0);G.adde(id(i, j) + B, id(i, j) + 2 * B, savem[i][j] / 2, 0);}else{if(start[i][j]==1){G.adde(id(i, j), id(i, j) + B, savem[i][j] / 2, 0);G.adde(id(i, j) + B, id(i, j) + 2 * B, savem[i][j] / 2 + 1, 0);}else {G.adde(id(i, j), id(i, j) + B, savem[i][j] / 2 + 1, 0);G.adde(id(i, j) + B, id(i, j) + 2 * B, savem[i][j] / 2, 0);}}}}cnt1 = 0;int cnt2 = 0;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){if(start[i][j]){cnt1++;G.adde(S, id(i, j) + B, 1, 0);}if(dest[i][j]){cnt2++;G.adde(id(i, j) + B, T, 1, 0);}}}if(cnt1!=cnt2){cout << -1 << endl;return 0;}int inf = 1e8;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){for (int changecnt = 0; changecnt < 8;changecnt++){int newi = i + change[changecnt][0];int newj = j + change[changecnt][1];if(0 < newi && newi<=n && 0<newj && newj<=m){G.adde(id(i, j) + 2 * B, id(newi, newj), inf, 1);}}}}FLOW.init(G);FLOW.maxflow(S, T);}