[网络流24题] 餐巾 - NekoMio's Blog

【问题描述】#

一个餐厅在相继的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的边
然后由前一天的剩下的向后一天连边
由前一天洗过的向能用的那一天连边
然后跑最小费用最大流就好了

1
#include <cstdio>
2
#include <cstring>
3
#include <queue>
4
using namespace std;
5
const int INF = 0x3f3f3f3f;
6
class Mincost
7
{
8
  public:
9
    int first[20005], p;
10
    Mincost()
11
    {
12
        memset(first, -1, sizeof(first));
13
    }
14
    class edge
15
    {
16
      public:
17
        int END, S, next, cap, cost;
18
    } v[100005];
19

20
    void add(int a, int b, int f, int c)
21
    {
22
        v[p].END = b, v[p].next = first[a], v[p].S = a, v[p].cap = f, v[p].cost = c, first[a] = p++;
23
        v[p].END = a, v[p].next = first[b], v[p].S = b, v[p].cap = 0, v[p].cost = -c, first[b] = p++;
24
    }
25
    int dis[20005], pre[20005];
26
    bool vis[20005];
27
    bool spfa(int S, int E)
28
    {
29
        memset(dis, 0x3f, sizeof(dis));
30
        memset(pre, -1, sizeof(pre));
31
        memset(vis, 0, sizeof(vis));
32
        queue<int> Q;
33
        Q.push(S);
34
        vis[S] = 1;
35
        dis[S] = 0;
36
        while (!Q.empty())
37
        {
38
            int u = Q.front();
39
            Q.pop();
40
            vis[u] = 0;
41
            for (int i = first[u]; i != -1; i = v[i].next)
42
            {
43
                if (!v[i].cap)
44
                    continue;
45
                if (dis[v[i].END] > dis[u] + v[i].cost)
46
                {
47
                    dis[v[i].END] = dis[u] + v[i].cost;
48
                    pre[v[i].END] = i;
49
                    if (!vis[v[i].END])
50
                    {
51
                        vis[v[i].END] = 1;
52
                        Q.push(v[i].END);
53
                    }
54
                }
55
            }
56
        }
57
        return dis[E] != 0x3f3f3f3f;
58
    }
59
    int MinCost(int S, int T)
60
    {
61
        int ans = 0, flow;
62
        while (spfa(S, T))
63
        {
64
            flow = INF;
65
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
66
                flow = min(flow, v[i].cap);
67
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
68
                v[i].cap -= flow, v[i ^ 1].cap += flow;
69
            ans += dis[T] * flow;
70
        }
71
        return ans;
72
    }
73
} Min;
74
int a[205];
75
int main(int argc, char const *argv[])
76
{
77
    freopen("napkin.in","r",stdin);
78
    freopen("napkin.out","w",stdout);
79
    int n, p, m, f, c, s;
80
    scanf("%d", &n);
81
    for (int i = 1; i <= n; i++)
82
    {
83
        scanf("%d", a + i);
84
    }
85
    scanf("%d%d%d%d%d", &p, &m, &f, &c, &s);
86
    int S = 0, T = n * 3;
87
    for (int i = 1; i <= n; i++)
88
    {
89
        Min.add(S, i, a[i], 0);
90
        Min.add(n + i, T, a[i], 0);
91
        Min.add(S, i + n, INF, p);
92
        //Min.add(i, i + n, a[i], 0);
93
        if (i + 1 <= n)
94
            Min.add(i, i + 1, INF, 0);
95
        if (i + m <= n)
96
            Min.add(i, i + n + m, INF, f);
97
        if (i + c <= n)
98
            Min.add(i, i + n + c, INF, s);
99
    }
100
    printf("%d", Min.MinCost(S, T));
101
    return 0;
102
}