[CODEVS1917] 深海机器人问题（最小费用最大流）

传送门

【问题分析】
最大费用最大流问题。
【建模方法】
把网格中每个位置抽象成网络中一个节点，建立附加源S汇T。
1、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为1，费用为该边价值的有向边。
2、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为无穷大，费用为0的有向边。
3、从S到每个出发点i连接一条容量为该点出发的机器人数量，费用为0的有向边。
4、从每个目标点i到T连接一条容量为可以到达该点的机器人数量，费用为0的有向边。
求最大费用最大流，最大费用流值就采集到的生物标本的最高总价值。
【建模分析】
这个问题可以看做是多出发点和目的地的网络运输问题。每条边的价值只能计算一次，容量限制要设为1。同时还将要连接上容量不限，费用为0的重边。由于“多个深海机器人可以在同一时间占据同一位置”，所以不需限制点的流量，直接求费用流即可。

吐槽：这出题人语文tm谁教的，输入看了我老半天

只需要知道权值不在点，而到了边上，而起点和终点变成了多个，起点和终点都有容量限制。

反而使题目变简单了（因为不再有没有权值的边，而且权值在边上比权值在点上多了一个好处——不用拆点）。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define INF 1e9 6 #define N 1000001 7 #define min(x, y) ((x) < (y) ? (x) : (y)) 8 9 int a, b, n, m, cnt, s, t; 10 int dis[N], pre[N]; 11 int head[N], to[N << 1], val[N << 1], cost[N << 1], next[N << 1]; 12 bool vis[N]; 13 14 inline int read() 15 22 23 inline int hash(int x, int y) 24 27 28 inline void add2(int x, int y, int z, int c) 29 36 37 inline void add(int x, int y, int z, int c) 38 42 43 inline bool spfa() 44 68 } 69 } 70 } 71 return pre[t] ^ 1; 72 } 73 74 inline int dinic() 75 86 sum += dis[t] * d; 87 } 88 return sum; 89 } 90 91 int main() 92 108 for(j = 1; j <= m; j++) 109 for(i = 0; i < n 1; i++) 110 115 while(a) 116 122 while(b) 123 129 printf("%d\n", dinic()); 130 return 0; 131 }
View Code

上一篇：后缀数组

下一篇：[BZOJ1031][JSOI2007]字符加密Cipher（后缀数组）

---

最小费用最大流 网络流