# [BZOJ1221]&&[HNOI2001] 软件开发

## 样例输入 SampleInput

10 2 5 10 7 5
71 17 93 10 82 38 92 4 66 14

## 样例输出 SampleOutput

3947

BZOJ 1221

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];
deque <int> q;
inline void ins(int u, int v, int f, int c)
{
e[cnt] = (edge)
{
};
e[cnt] = (edge)
{
};
}
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;
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;
}``````