[网络流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;
}