[luoguP3159] [CQOI2012]交换棋子（最小费用最大流）

传送门

好难的网络流啊，建图真的超难。

如果不告诉我是网络流的话，我估计就会写dfs了。

使用费用流解决本题，设点 $p[i][j]$ 的参与交换的次数上限为 $v[i][j]$ ，以下为建图方式：

1. 将一个点分成三个点，分别为入点，原点和出点。

2. 如果开始的图上该位置有棋子，那么从S到该点的原点连一条边权1，费用0的边

3. 如果结束的图上该位置有棋子，那么从该点的原点到T连一条边权1，费用0的边

4. 如果该点只在开始的图上出现，那么从该点的入点向原点连一条边权为 $v[i][j]/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $(v[i][j]+1)/2$ ，费用为0的边

5. 如果该点只在结束的图上出现，那么从该点的入点向原点连一条边权为 $(v[i][j]+1)/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $v[i][j]/2$ ，费用为0的边

6. 如果以上两点都不符合，那么从该点的入点向原点连一条边权为 $v[i][j]/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $v[i][j]/2$ ，费用为0的边

——byzhouyonglong

我只是题解的搬运工。

最后把每个点的原点和它相邻的点的原点连一条容量为INF，费用为0的边

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 1000001#define id(i, j, k) ((i  1) * m + j + (k  1) * n * m)using namespace std;int n, m, cnt, s, t, ans, sum1, sum2, sum;int head[N], to[N], nex[N], val[N], cost[N], dis[N], pre[N], path[N];char s1[21][21], s2[21][21], c[21][21];const int dx[8] = , dy[8] = ;bool vis[N];inline int read()inline void add(int x, int y, int z, int v)inline bool spfa()}}}return pre[t] != 1;}inline void E()int main()if(s2[i][j] == '1')if(s1[i][j] == '1' && s2[i][j] == '0')if(s1[i][j] == '0' && s2[i][j] == '1')if(s1[i][j] == s2[i][j])for(k = 0; k < 8; k++)}}if(sum1 != sum2) E();while(spfa())}if(sum != sum1) E();printf("%d\n", ans);return 0;}

上一篇：[BZOJ2118] 墨墨的等式（最短路）

下一篇：[luoguP3413] SAC#1 - 萌数（数位DP）