784 字
4 分钟
[网络流24题] 餐巾
【问题描述】
一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l,2,…,N)。餐厅可以从三种途径获得餐巾。
- 购买新的餐巾,每块需p分;
- 把用过的餐巾送到快洗部,洗一块需m天,费用需f分(f<p)。如m=l时,第一天送到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。
- 把餐巾送到慢洗部,洗一块需n天(n>m),费用需s分(s<f)。在每天结束时,餐厅必须决定多少块用过的餐巾送到快洗部,多少块送慢洗部。在每天开始时,餐厅必须决定是否购买新餐巾及多少,使洗好的和新购的餐巾之和满足当天的需求量Ri,并使N天总的费用最小。
【输入】
输入文件共 3 行,第 1 行为总天数;第 2 行为每天所需的餐巾块数;第 3 行为每块餐巾的新购费用 p ,快洗所需天数 m ,快洗所需费用 f ,慢洗所需天数 n ,慢洗所需费用 s 。
【输出】
一行,最小的费用
【样例】
napkin.in
3
3 2 4
10 1 6 2 3
napkin.out
64
【数据规模】
n<=200,Ri<=50
题解
将天拆点
由源点向天的第一个点连边
然后由天的第二个点向汇点连边
流量都为Ri 费用为零
由源点向天的第二个点连流量为正无穷 费用为p的边
然后由前一天的剩下的向后一天连边
由前一天洗过的向能用的那一天连边
然后跑最小费用最大流就好了
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
class Mincost
{
public:
int first[20005], p;
Mincost()
{
memset(first, -1, sizeof(first));
}
class edge
{
public:
int END, S, next, cap, cost;
} v[100005];
void add(int a, int b, int f, int c)
{
v[p].END = b, v[p].next = first[a], v[p].S = a, v[p].cap = f, v[p].cost = c, first[a] = p++;
v[p].END = a, v[p].next = first[b], v[p].S = b, v[p].cap = 0, v[p].cost = -c, first[b] = p++;
}
int dis[20005], pre[20005];
bool vis[20005];
bool spfa(int S, int E)
{
memset(dis, 0x3f, sizeof(dis));
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(S);
vis[S] = 1;
dis[S] = 0;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = 0;
for (int i = first[u]; i != -1; i = v[i].next)
{
if (!v[i].cap)
continue;
if (dis[v[i].END] > dis[u] + v[i].cost)
{
dis[v[i].END] = dis[u] + v[i].cost;
pre[v[i].END] = i;
if (!vis[v[i].END])
{
vis[v[i].END] = 1;
Q.push(v[i].END);
}
}
}
}
return dis[E] != 0x3f3f3f3f;
}
int MinCost(int S, int T)
{
int ans = 0, flow;
while (spfa(S, T))
{
flow = INF;
for (int i = pre[T]; i != -1; i = pre[v[i].S])
flow = min(flow, v[i].cap);
for (int i = pre[T]; i != -1; i = pre[v[i].S])
v[i].cap -= flow, v[i ^ 1].cap += flow;
ans += dis[T] * flow;
}
return ans;
}
} Min;
int a[205];
int main(int argc, char const *argv[])
{
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
int n, p, m, f, c, s;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
scanf("%d%d%d%d%d", &p, &m, &f, &c, &s);
int S = 0, T = n * 3;
for (int i = 1; i <= n; i++)
{
Min.add(S, i, a[i], 0);
Min.add(n + i, T, a[i], 0);
Min.add(S, i + n, INF, p);
//Min.add(i, i + n, a[i], 0);
if (i + 1 <= n)
Min.add(i, i + 1, INF, 0);
if (i + m <= n)
Min.add(i, i + n + m, INF, f);
if (i + c <= n)
Min.add(i, i + n + c, INF, s);
}
printf("%d", Min.MinCost(S, T));
return 0;
}