P1251 餐巾计划问题

发表于 | 阅读数

每天可以买毛巾($p$元一个)，或者洗好的毛巾。可以选择两个洗毛巾的地方

  • 需要$n$天，每个收费$f$元。
  • 需要$m$天，每个收费$s$元。

每天有额定的需要毛巾数量$a[i]$。

求最小的花费。

费用流第一道题。

首先干了两件事，用毛巾和洗毛巾考虑拆点。

首先最大流是为了限制每天满足要求。

  • $i\rightarrow^{a[i]}_0 t$

每天晚上又只能洗$a[i]$个毛巾

  • $s\rightarrow^{a[i]}_0 (i+N)$

然后就是按题意连边。

  • $s\rightarrow^{INF}_p (i+N)$
  • $i\rightarrow^{INF}_f (i+n)$
  • $i\rightarrow^{INF}_s (i+m)$

注意毛巾洗多了可以留到明天

  • $i\rightarrow^{INF}_0 (i+1)$
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
#define INF 0x3f3f3f3f
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
struct Edge
{
    int to, w, nxt, f;
    Edge() {}
    Edge(int v, int c, int t, int k) : to(v), w(c), nxt(t), f(k) {}
};
const int EN = 5e3 + 10;
const int EM = 5e4 + 10;
struct LeiDinic
{

    Edge e[EM << 1];
    int head[EN], scnt, dis[EN], vis[EN], cur[EN];
    ll cost;
    LeiDinic() { scnt = 1, cost = 0; }
    void addEdge(int u, int v, int w, int k)
    {
        e[++scnt] = Edge(v, w, head[u], k);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v], -k); ///!!!!
        head[v] = scnt;
    }
    bool spfa(int s, int t)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, INF, sizeof(dis));
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;

        q.push(s);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;

                if (dis[to] > dis[x] + e[i].f && e[i].w)
                {
                    dis[to] = dis[x] + e[i].f;
                    if (!vis[to])
                    {
                        vis[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        return dis[t] != INF;
    }

    int dfs(int x, int t, int flow)
    {
        if (x == t)
            return flow;
        vis[x] = 1;
        int res = 0;
        for (int i = cur[x]; i && res < flow; i = e[i].nxt)
        {
            cur[x] = i;
            int to = e[i].to;
            if (!vis[to] && dis[to] == dis[x] + e[i].f && e[i].w)
            {
                int dis = dfs(to, t, min(flow - res, e[i].w));
                if (dis)
                {
                    e[i].w -= dis;
                    e[i ^ 1].w += dis;
                    cost += 1ll * e[i].f * dis;
                    res += dis;
                }
            }
        }
        vis[x] = 0;
        return res;
    }
    ll Maxflow(int s, int t)
    {
        int ans = 0, tmp;
        while (spfa(s, t))
        {
            memcpy(cur, head, sizeof(head));
            while ((tmp = dfs(s, t, INF)))
                ans += tmp;
        }
        return cost;
    }
} dc;
int a[N];
int main()
{
    int Q = read();
    for (int i = 1; i <= Q; i++)
        a[i] = read();
    int p = read(), m = read(), f = read(), n = read(), sf = read();
    int s = 2 * Q + 1, t = 2 * Q + 2;
    for (int i = 1; i <= Q; i++)
    {
        dc.addEdge(s, i, INF, p);
        dc.addEdge(i, t, a[i], 0);
        dc.addEdge(s, i + Q, a[i], 0);
        if (i + m <= Q)
            dc.addEdge(i + Q, i + m, INF, f);
        if (i + n <= Q)
            dc.addEdge(i + Q, i + n, INF, sf);
        if (i + 1 <= Q)
            dc.addEdge(i, i + 1, INF, 0);
    }
    printf("%lld\n", dc.Maxflow(s, t));
}