翻车笔记_ 餐巾计划问题 [费用流, 翻车]

有些题目不是那么想当然就能做出来的

对算法的理解是最重要的

懵逼的 题目

传送至 Luogu

扯淡的 题解

刚开始我觉得这个题很吼啊, 难度虚高啊 @丁旭高 不就是分成新毛巾和旧毛巾然后新毛巾变成旧毛巾, 旧毛巾洗成新毛巾嘛~于是新毛巾和S连边, 旧毛巾和T和洗完的天数连边…就成了下面这个样子…_(:з」∠)_

这里写图片描述

后来一看不对啊…这个根本不能跑最大流啊…跑最大流的话一定会变成这样: 每一天都买毛巾, 然后全用光, 然后也不洗, 就扔掉(因为这里的流量代表毛巾的使用数量, 所以最大流量就要求毛巾最多, 这肯定是不符合题意的)…GG然后就想…符合题意的话就让新旧毛巾两点之间的边满载就好了…上下界? 不会…GG

然后就翻题解…然后知道了应该这么连边…Emmmmmm…

这里写图片描述

具体连边就是(设新毛巾是X, 旧毛巾是Y):

  1. S -> Xi, 容量为这一天的需求, 费用为买毛巾的钱, 代表这一天最多买需要的新毛巾数量(多买了也没用不是?)
  2. Xi -> T, 容量为需求, 费用为0, 代表…没有代表, 就是用完了…找个地方放(你总得让流量到T不是?_(:з」∠)_)(注意类边上的流量什么都不代表, 这条边上的毛巾我们并不知道他是扔了还是洗了)
  3. S -> Yi, 容量为需求, 费用是0, 代表要洗的毛巾
  4. Xi -> X (i + 1), (放不了LaTeX你们将就QAQ)容量为INF, 费用为0, 代表这一天干净的毛巾留到下一天
  5. Yi -> X (i + 快洗天数), 容量为需求, 费用为快洗费用, 代表这一天不干净的毛巾快洗, 到n久后取到
  6. Yi -> X (i + 慢洗天数)…同上

之所以这么连是因为: 新毛巾不会”变成”旧毛巾…因为旧毛巾的去路一共就两种一个扔了一个洗了, 肯定扔了的最大流量更大, 所以不能在新旧毛巾之间连边…而新图中, 扔或者洗旧毛巾只会对新毛巾的来路产生影响, 而不会影响到最大流量…

然后就是跑费用流…注意龙龙long long

沙茶的 代码

并没有优化, 最慢1612ms真是喜闻乐见

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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN (2000 + 5)
#define MAXM (80000 + 5)
#define LL long long
#define rev(a) (((a - 1) ^ 1) + 1)
#define bh(a) ((a < MAXN) ? (a + MAXN) : (a))
#define ubh(a) ((a > MAXN) ? (a) : (a - MAXN))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7ffffff)
const int s = 0, t = (MAXN << 1) - 5;
using namespace std;
struct edg
{
int from;
int to;
int next;
int cost;
int flow;
int cap;
edg() {}
edg(int a, int b, int c, int d, int e, int f): from(a), to(b), next(c), cost(d), flow(e), cap(f) {}
}b[MAXM];
int g[MAXN << 1];
int cntb;

int n;
int fc, sc, fd, sd;
int nc;
int dn[MAXN];
LL ans;
int pre[MAXN << 1];
int a[MAXN << 1];
void adn(int, int, int, int);
void init();
bool spfa(int);
void solve();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &dn[i]);
}
scanf("%d%d%d%d%d", &nc, &fd, &fc, &sd, &sc);
init();
solve();
printf("%lld\n", ans);
return 0;
}
void adn(int from, int to, int cost, int cap)
{
b[++cntb] = edg(from, to, g[from], cost, 0, cap);
g[from] = cntb;
}
void init()
{
for (int i = 1; i <= n; i++)
{
adn(s, i, nc, dn[i]);
adn(i, s, -nc, 0);

adn(i, t, 0, dn[i]);
adn(t, i, 0, 0);

adn(s, bh(i), 0, dn[i]);
adn(bh(i), s, 0, 0);

if (i < n)
{
adn(i, i + 1, 0, INF);
adn(i + 1, i, 0, 0);
}

if (i + fd <= n)
{
adn(bh(i), i + fd, fc, dn[i]);
adn(i + fd, bh(i), -fc, 0);
}

if (i + sd <= n)
{
adn(bh(i), i + sd, sc, dn[i]);
adn(i + sd, bh(i), -sc, 0);
}
}
}
bool spfa(int start)
{
int dis[MAXN << 1];
bool inq[MAXN << 1];
memset(dis, 0x7f, sizeof(dis));
memset(inq, false, sizeof(inq));
memset(a, 0, sizeof(a));
queue<int> q;
q.push(start);
inq[start] = true, dis[start] = 0, a[start] = INF;
while (!q.empty())
{
int dq = q.front();
q.pop();
inq[dq] = false;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] > dis[dq] + b[i].cost)
{
a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
dis[b[i].to] = dis[dq] + b[i].cost;
pre[b[i].to] = i;
if (!inq[b[i].to])
{
q.push(b[i].to);
inq[b[i].to] = true;
}
}
}
}
return a[t];
}
void solve()
{
while (spfa(s))
{
for (int i = t; i != s; i = b[pre[i]].from)
{
b[pre[i]].flow += a[t];
b[rev(pre[i])].flow -= a[t];
ans += (LL)b[pre[i]].cost * a[t];
}
}
}

By 没写作业还逃课好感度估计已经掉没的 Cansult