[luoguP1251] 餐巾计划问题（费用流）
传送门
模型
网络优化问题，用最小费用最大流解决。
实现
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。
求网络最小费用最大流，费用流值就是要求的最小总花费。
分析
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi>Xi+1），不需要花费，送到快洗部(Xi>Yi+m)，费用为f，送到慢洗部(Xi>Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S>Yi)，费用为p。
在网络上求出的最小费用最大流，满足了问题的约束条件（因为在这个图上最大流一定可以使与T连接的边全部满流，其他边只要有可行流就满足条件），而且还可以保证总费用最小，就是我们的优化目标。
还是得好好理解这个建图。
然而这个代码在洛谷上超时了，不会zkw费用流QAQ
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 4010 6 #define M 100005 7 #define INF ~(1 << 31) 8 #define min(x, y) ((x) < (y) ? (x) : (y)) 9 10 int a, p, m, f, n, g, s, t, cnt; 11 int head[N], to[M], val[M], cost[M], next[M], dis[N], pre[N]; 12 bool vis[N]; 13 long long sum; 14 15 inline int read() 16 23 24 inline void add(int x, int y, int z, int c) 25 32 33 inline bool spfa() 34 58 } 59 } 60 } 61 return pre[t] ^ 1; 62 } 64 int main() 65 76 p = read(); 77 m = read(); 78 f = read(); 79 n = read(); 80 g = read(); 81 for(i = a + 1; i <= a + a; i++) add(s, i, INF, p), add(i, s, 0, p); 82 for(i = 1; i < a; i++) add(i, i + 1, INF, 0), add(i + 1, i, 0, 0); 83 for(i = 1; i <= a m; i++) add(i, i + a + m, INF, f), add(i + a + m, i, 0, f); 84 for(i = 1; i <= a n; i++) add(i, i + a + n, INF, g), add(i + a + n, i, 0, g); 85 while(spfa()) 86 94 sum += (long long)dis[t] * d; 95 } 96 printf("%lld\n", sum); 97 return 0; 98 }View Code
下一篇：[luoguP2761] 软件补丁问题（状压最短路）
最小费用最大流 最大流 网络流