[HNOI2001] 软件开发
题面：
某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。
思路：
这题的建图还是十分困难的
首先对于一个点我们肯定是要拆成两个点的
然后对于买的毛巾与洗后的毛巾应该处于统一层
所以s(源)向每个(i+n)连(f,inf)的边
每个(i)向(i+a+n+1)连(fa, inf)的边
每个(i)向(i+b+n+1)连(fb, inf)的边
由于一天没用的毛巾可以留到下一天所以对于
每个(i)向(i+1)连(0,inf)的边
最后
每个(s)向(i)连(0,di[i])的边
每个(i+n)向(t)连(0,di[i])的边
建图完成
代码：
#include<cstdio>
#include<cstring>
#define REP(i,a,b) for(register int i = a; i <= b; ++i)
const int MAXN = 2e3 + 50;
const int inf = 0x3f3f3f3f;
inline int min(int a, int b) {return a > b ? b : a;}
inline int max(int a, int b) {return a > b ? a : b;}
inline int read() {
int x = 0 , f = 1; char c; while((c = getchar()) > '9' || c < '0') if(c == '-') f = 0; x = c - 48;
while((c = getchar()) >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - 48; return f ? x : ~x + 1;
}
int s, t, n, a, b, ff, fa, fb, ans = 0, ni[MAXN];
int Head[MAXN], cnt = 0;
struct edge {int to, nxt, cap, dis;} E[50005];
inline void add(int u, int v, int c, int f) {
E[cnt] = edge {v, Head[u], c, f}; Head[u] = cnt ++;
E[cnt] = edge {u, Head[v], 0, -f}; Head[v] = cnt ++;
}
int Q[1000005], d[MAXN], pre[MAXN], cur[MAXN], l = 1, r = 0; bool inq[MAXN];
inline bool spfa() {
REP(i,0,t) d[i] = inf, pre[i] = 0, cur[i] = 0, inq[i] = false;
d[Q[++r]=s] = 0;
while(l <= r) {
int u = Q[l++]; inq[u] = false;
for(register int i = Head[u]; ~i; i = E[i].nxt) {
int v = E[i].to; if(E[i].cap<=0||d[v]<=d[u]+E[i].dis) continue;
d[v]=d[u]+E[i].dis; pre[v] = u; cur[v] = i;
if(inq[v]) continue; inq[v] = true;
if(l&&d[Q[l]]>=d[v]) Q[--l] = v; else Q[++r] = v;
}
}
return d[t] < inf;
}
inline int Augment() {
int u = t, low = inf, res = 0;
while(u != s) low = min(low, E[cur[u]].cap), u = pre[u]; u = t;
while(u != s) E[cur[u]].cap -= low, E[cur[u]^1].cap += low, res += E[cur[u]].dis*low, u = pre[u];
return res;
}
int main() {
memset(Head, -1, sizeof(Head));
n = read(); a = read(); b = read();
ff= read(); fa= read(); fb= read();
REP(i,1,n) ni[i] = read();
s = 0; t = n*2+1;
REP(i,1,n) add(s, i, ni[i], 0);
REP(i,1,n-1) add(i, i+1, inf, 0);
REP(i,1,n) add(i+n, t, ni[i], 0);
REP(i,1,n) add(s, i+n, inf, ff);
for(register int i = 1; i+a+1 <= n; ++i)
add(i, i+a+n+1, inf, fa);
for(register int i = 1; i+b+1 <= n; ++i)
add(i, i+b+n+1, inf, fb);
while(spfa()) ans += Augment();
printf("%d\n", ans);
return 0;
}