首页 > 代码库 > ACdream 1128 Maze（费用流）
ACdream 1128 Maze（费用流）
题目链接：http://acdream.info/problem?pid=1128
Problem Description
wuyiqi陷入了一个迷宫中，这个迷宫是由N*M个格子组成的矩阵。每个格子上堆放了一定数量的箱子。(i,j)表示第i行，第j列的格子。wuyiqi可以将一个格子上的箱子移动到相邻的格子上，或者在这个格子上销毁。也就是在(i,j)的箱子可以移动到(i-1,j)、(i+1,j)、(i,j-1)和(i,j+1)，但是不能移动到矩阵范围外。将(i,j)的格子上的一个箱子移动到相邻格子需要消耗x的RP值，将一个箱子销毁需要消耗y的RP值。当每行的箱子数相等，每列的箱子数相等的时候，wuyiqi就可以逃出去了。求帮wuyiqi算出逃出去需要消耗的最小RP值吧。
Input
有多组数据。
每组数据第一行是两个正整数N和M（1<=N,M<=100）。
接下来一行两个整数为x和y（1<=x,y<=100）
接下来N行，每行有M个非负整数，第i行的第j个数为p(i,j)（0<=p(i,j)<=20）代表(i,j)格子上有的箱子数。Output
输出wuyiqi逃离需要消耗的最小RP值。
题目大意：略。
思路：考虑结果的话，每行的总和是一样的，每列的总和是一样的。那么每行的总和是n的倍数，每列的总和是m的倍数。那么整个棋盘的总和一定是lcm(n, m)的倍数。
那么枚举最终棋盘剩余的箱子数，枚举lcm(n, m)的倍数，假设为b，那么需要销毁的箱子数为(sum - b) * y，其中sum为总箱子数。
现在考虑每一行间箱子的移动，设sumr[i]为第 i 行的箱子总和，现在要求每一行都变成b / n。
建图，建一个源点，连一条边到每一行的容量为sumr[i]，费用为0。建一个汇点，每一行到汇点连一条边，容量为b / n，费用为0。
相邻的行之间连一条边，容量为正无穷大，费用为x。
跑最小费用最大流可得到箱子在行之间移动的代价。同理可以得到箱子在列之间移动的代价。
取枚举之后的总代价的最小值。
PS：肉眼DEBUG的时候发现以前一直在用的SPFA费用流模板是错的……
代码（96MS）：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <queue> 6 #include <numeric> 7 using namespace std; 8 typedef long long LL; 9 10 const int MAXN = 110; 11 const int MAXV = 110; 12 const int MAXE = 8 * MAXV; 13 const int INF = 0x7f7f7f7f; 14 15 struct SPFA_COST_FLOW { 16 int head[MAXV]; 17 int to[MAXE], next[MAXE], cost[MAXE], flow[MAXE]; 18 int n, ecnt, st, ed; 19 20 void init(int nn) { 21 n = nn; 22 memset(head + 1, -1, n * sizeof(int)); 23 ecnt = 0; 24 } 25 26 void add_edge(int u, int v, int c, int w) { 27 to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++; 28 to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++; 29 } 30 31 bool vis[MAXV]; 32 int dis[MAXV], pre[MAXV]; 33 queue<int> que; 34 35 bool spfa() { 36 memset(vis + 1, 0, n * sizeof(bool)); 37 memset(dis + 1, 0x7f, n * sizeof(int)); 38 dis[st] = 0; que.push(st); 39 while(!que.empty()) { 40 int u = que.front(); que.pop(); 41 vis[u] = false; 42 for(int p = head[u]; ~p; p = next[p]) { 43 int &v = to[p]; 44 if(flow[p] && dis[v] > dis[u] + cost[p]) { 45 dis[v] = dis[u] + cost[p]; 46 pre[v] = p; 47 if(!vis[v]) { 48 que.push(v); 49 vis[v] = true; 50 } 51 } 52 } 53 } 54 return dis[ed] < INF; 55 } 56 57 int maxFlow, minCost; 58 int min_cost_flow(int ss, int tt) { 59 st = ss, ed = tt; 60 maxFlow = minCost = 0; 61 while(spfa()) { 62 int u = ed, tmp = INF; 63 while(u != st) { 64 tmp = min(tmp, flow[pre[u]]); 65 u = to[pre[u] ^ 1]; 66 } 67 u = ed; 68 while(u != st) { 69 flow[pre[u]] -= tmp; 70 flow[pre[u] ^ 1] += tmp; 71 u = to[pre[u] ^ 1]; 72 } 73 maxFlow += tmp; 74 minCost += tmp * dis[ed]; 75 } 76 return minCost; 77 } 78 } G; 79 80 int mat[MAXN][MAXN]; 81 int sumr[MAXN], sumc[MAXN]; 82 int n, m, x, y; 83 84 int calc(int sum[], int n, int c) { 85 int ss = n + 1, tt = n + 2; 86 G.init(n + 2); 87 for(int i = 1; i <= n; ++i) 88 G.add_edge(ss, i, sum[i], 0), G.add_edge(i, tt, c, 0); 89 for(int i = 1; i < n; ++i) 90 G.add_edge(i, i + 1, INF, x), G.add_edge(i + 1, i, INF, x); 91 return G.min_cost_flow(ss, tt); 92 } 93 94 int solve() { 95 int sum = accumulate(sumr + 1, sumr + n + 1, 0), ans = sum * y; 96 int lcm = n * m / __gcd(n, m); 97 for(int b = lcm; b <= sum; b += lcm) { 98 ans = min(ans, (sum - b) * y + calc(sumr, n, b / n) + calc(sumc, m, b / m)); 99 }100 return ans;101 }102 103 int main() {104 while(scanf("%d%d", &n, &m) != EOF) {105 scanf("%d%d", &x, &y);106 for(int i = 1; i <= n; ++i)107 for(int j = 1; j <= m; ++j) scanf("%d", &mat[i][j]);108 memset(sumr + 1, 0, n * sizeof(int));109 memset(sumc + 1, 0, m * sizeof(int));110 for(int i = 1; i <= n; ++i) {111 for(int j = 1; j <= m; ++j) {112 sumr[i] += mat[i][j];113 sumc[j] += mat[i][j];114 }115 }116 printf("%d\n", solve());117 }118 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。