首页 > 代码库 > [luoguP1251] 餐巾计划问题（费用流）
[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 {17 int x = 0, f = 1;18 char ch = getchar();19 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;20 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;21 return x * f;22 }23 24 inline void add(int x, int y, int z, int c)25 {26 to[cnt] = y;27 val[cnt] = z;28 cost[cnt] = c;29 next[cnt] = head[x];30 head[x] = cnt++;31 }32 33 inline bool spfa()34 {35 int i, u, v;36 std::queue <int> q;37 memset(vis, 0, sizeof(vis));38 memset(pre, -1, sizeof(pre));39 memset(dis, 127 / 3, sizeof(dis));40 q.push(s);41 dis[s] = 0;42 while(!q.empty())43 {44 u = q.front(), q.pop();45 vis[u] = 0;46 for(i = head[u]; i ^ -1; i = next[i])47 {48 v = to[i];49 if(val[i] && dis[v] > dis[u] + cost[i])50 {51 dis[v] = dis[u] + cost[i];52 pre[v] = i;53 if(!vis[v])54 {55 q.push(v);56 vis[v] = 1;57 }58 }59 }60 }61 return pre[t] ^ -1;62 }63 64 int main()65 {66 int i, x, d;67 a = read();68 s = 0, t = (a << 1) + 1;69 memset(head, -1, sizeof(head));70 for(i = 1; i <= a; i++)71 {72 x = read();73 add(s, i, x, 0), add(i, s, 0, 0);74 add(i + a, t, x, 0), add(t, i + a, 0, 0);75 }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 {87 d = 1e9;88 for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) d = min(d, val[i]);89 for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]])90 {91 val[i] -= d;92 val[i ^ 1] += d;93 }94 sum += (long long)dis[t] * d;95 }96 printf("%lld\n", sum);97 return 0;98 }
[luoguP1251] 餐巾计划问题（费用流）