描述 Description
某软件公司正在规划一项 n 天的软件开发计划，根据开发计划第 i 天需要 ni 个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A 种方式的消毒需要 a 天时间，B 种方式的消毒需要 b 天（b>a），A 种消毒方式的费用为每块毛巾 fA, B 种消毒方式的费用为每块毛巾 fB，而买一块新毛巾的费用为 f（新毛巾是已消毒的，当天可以使用）；而且 f>fA>fB。公司经理正在规划在这 n 天中，每天买多少块新毛巾、每天送多少块毛巾进行 A 种消毒和每天送多少块毛巾进行 B 种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行 A 种消毒和多少毛巾进行 B 种消毒，使公司在这项 n 天的软件开发中，提供毛巾服务的总费用最低。
输入格式 InputFormat
第 1 行为 n,a,b,f,fA,fB. 第 2 行为 n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）
输出格式 OutputFormat
最少费用
样例输入 SampleInput
10 2 5 10 7 5
71 17 93 10 82 38 92 4 66 14
样例输出 SampleOutput
3947
把每天分为二分图两个集合中的顶点 Xi,Yi，建立附加源 S 汇 T。二分图 X 集合中顶点 Xi 表示第 i 天用完的餐巾, Y 集合中每个点 Yi 则是第 i 天需要的餐巾.
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 的有向边。
求网络最小费用最大流，费用流值就是要求的最小总花费。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 2005;
const int maxm = 6 * maxn;
int i, j, t, n, m, l, r, k, z, y, x;
int cnt, num, a, b, f, fa, fb;
struct edge
{
int to, fl, co, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], pre[maxn];
deque <int> q;
inline void ins(int u, int v, int f, int c)
{
e[cnt] = (edge)
{
v, f, c, head[u]
};
head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, -c, head[v]
};
head[v] = cnt++;
}
inline bool spfa(int s, int t, int tim)
{
int i, u, v, w;
while (!q.empty()) q.pop_front();
for (i = s; i <= t; i++) dis[i] = inf;
dis[s] = 0; used[s] = tim; pre[s] = -1;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front(); used[u] = 0;
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to; w = e[i].co;
if (dis[v] > dis[u] + w && e[i].fl > 0)
{
dis[v] = dis[u] + w;
pre[v] = i;
if (used[v] != tim)
{
used[v] = tim;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return (dis[t] != inf);
}
inline void mcmf(int s, int t)
{
int i, f, ans = 0;
while (spfa(s, t, ++num))
{
// cout << " " << ans << endl;
for (f = inf, i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) f = min(f, e[i].fl);
for (i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) e[i].fl -= f, e[i ^ 1].fl += f;
ans += f * dis[t];
}
printf("%d\n", ans);
}
int main()
{
cnt = num = 0;
memset(head, -1, sizeof(head));
scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb);
for (i = 1; i <= n; i++)
{
scanf("%d", &x);
ins(0, i, x, 0);
ins(n + i, 2 * n + 1, x, 0);
ins(0, n + i, inf, f);
}
for (i = 1; i < n; i++) ins(i, i + 1, inf, 0);
for (i = 1; i + a + 1 <= n; i++) ins(i, n + i + a + 1, inf, fa);
for (i = 1; i + b + 1 <= n; i++) ins(i, n + i + b + 1, inf, fb);
mcmf(0, 2 * n + 1);
return 0;
}