1221: [HNOI2001] 软件开发
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1428 Solved: 791
[Submit][Status][Discuss]
Description
某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。
Input
第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）
Output
最少费用
Sample Input
8 2 1 6
Sample Output
HINT
Source
最小费用最大流，各种调代码。
把每一天拆点，分为Xi和Yi。可以理解X为未消毒，Y为已消毒。
源点向Xi供应Ni个费用为0的流量，代表每天产生的用过的毛巾。
Yi向汇点连容量Ni的费用为0的边，代表每天使用的毛巾。
源点向Yi连费用为F的边，容量无穷，代表可以新购毛巾。
Xi向Yi+A+1连费用为Fa的边，代表可以在i时送去消毒，i+A+1时使用；B同理。
Xi向Xi+1连边，代表今天的脏毛巾可以留着回头再拿来洗。
#include <bits/stdc++.h> inline int get_c(void)
{
static const int siz = ; static char buf[siz];
static char *head = buf + siz;
static char *tail = buf + siz; if (head == tail)
fread(head = buf, , siz, stdin); return *head++;
} inline int get_i(void)
{
register int ret = ;
register int neg = false;
register int bit = get_c(); for (; bit < ; bit = get_c())
if (bit == '-')neg ^= true; for (; bit > ; bit = get_c())
ret = ret * + bit - ; return neg ? -ret : ret;
} const int inf = 2e9;
const int maxn = ; int n, a, b, f, c, d; int s, t;
int edges;
int hd[maxn];
int to[maxn];
int fl[maxn];
int vl[maxn];
int nt[maxn]; inline void add(int u, int v, int f, int w) {
nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; vl[edges] = +w; hd[u] = edges++;
nt[edges] = hd[v]; to[edges] = u; fl[edges] = ; vl[edges] = -w; hd[v] = edges++;
} int dis[maxn];
int pre[maxn]; inline bool bfs(void) {
static int que[maxn];
static int inq[maxn];
static int head, tail; for (int i = s; i <= t; ++i)dis[i] = inf;
memset(inq, , sizeof(inq));
que[tail++] = s;
pre[s] = -;
dis[s] = ;
inq[s] = ; while (head != tail) {
int u = que[head++], v; inq[u] = ;
if (head == maxn)head = ;
for (int i = hd[u]; ~i; i = nt[i])
if (fl[i] && dis[v = to[i]] > dis[u] + vl[i]) {
dis[v] = dis[u] + vl[i];
pre[v] = i ^ ;
if (!inq[v]) {
inq[que[tail++] = v];
if (tail == maxn)
tail = ;
}
}
} return dis[t] < inf;
} inline int minCost(void) {
int cost = ; while (bfs()) {
int flow = inf; for (int i = pre[t]; ~i; i = pre[to[i]])
flow = std::min(flow, fl[i ^ ]); for (int i = pre[t]; ~i; i = pre[to[i]])
fl[i] += flow, fl[i ^ ] -= flow; cost += flow * dis[t];
} return cost;
} signed main(void)
{
memset(hd, -, sizeof(hd)); n = get_i();
a = get_i();
b = get_i();
f = get_i();
c = get_i();
d = get_i(); s = , t = (n + ) * + ; for (int i = ; i <= n; ++i) {
int x = get_i();
add(s, i, x, );
add(i + n, t, x, );
add(s, i + n, inf, f);
if (i + <= n)
add(i, i + , inf, );
if (i + a + <= n)
add(i, i + a + + n, inf, c);
if (i + b + <= n)
add(i, i + b + + n, inf, d);
} printf("%d\n", minCost());
}
@Author: YouSiki