水题笔记_ [SDOI2011]工作安排 [费用流, 网络流]

丰年好大水

果然题越简单数据越鬼…

懵逼的 题目

qwq

扯淡的 题解

题目好长…其实说白了费用就是底下这个玩意

$$
C(x) = \begin{cases}
W_1\,\,x \in [1, T_1]\\
W_2\,\,x \in [T_1 + 1, T_2]\\
W_3\,\,x \in [T_2 + 1, T_3]\\
\cdots \\
W_i\,\,x \in [T_{i - 1} + 1, T_{i}]\\
W_{S_{dq}}\,\,x \in [T_{S_{dq}}, \infty]
\end{cases}
$$

是不是很懵逼? 是不是想到修车 || 美食节去了?

看到底下有一句话$W_{i, j} > W_{i, j - 1}$就很简单了…直接连就好了…

  • $S \to i\,\,\,\,(cost = 0, cap = \infty)$
  • $i \to i’\,\,\,(cost = W_{i, j}, cap = T_{i, j} - T_{i, j - 1})$
  • $i’ \to things_j\,\,\,(cost = 0, cap = \infty), A_{i, j} = true$
  • $things_j \to T\,\,\,(cost = 0, cap = \infty)$

沙茶的 代码

数据真的鬼

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
/**************************************************************
Problem: 2245
User: Cansult
Language: C++
Result: Accepted
Time:12724 ms
Memory:54544 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7fffffff)
#define bh(x) ((x) + 500)
#define sub(x) ((x) + 1000)
#define rev(a) ((a) ^ 1)
#define int long long
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from, to, next, cost, cap, flow;
edg() {}
edg(int fr, int dqt, int ne, int co, int ca): from(fr), to(dqt), next(ne), cost(co), cap(ca), flow(0) {}
}b[MAXM << 1];
int g[MAXN], cntb = -1, dis[MAXN], a[MAXN], pre[MAXN], ans;
int spfa()
{
bool inq[MAXN];
memset(inq, false, sizeof(inq));
memset(dis, 0x7f, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 0;
a[t] = 0, a[s] = 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)
{
dis[b[i].to] = dis[dq] + b[i].cost;
pre[b[i].to] = i;
a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
if (!inq[b[i].to])
q.push(b[i].to), inq[b[i].to] = true;
}
}
return a[t];
}
void adn(int from, int to, int cap, int cost)
{
b[++cntb] = edg(from, to, g[from], cost, cap);
g[from] = cntb;
}
void solve()
{
while (true)
{
int zl = spfa();
if (!zl)
break;
for (int i = t; i != s; i = b[pre[i]].from)
b[pre[i]].flow += zl, b[rev(pre[i])].flow -= zl, ans += zl * b[pre[i]].cost;
}
}
main()
{
memset(g, -1, sizeof(g));
int n, m;
scanf("%lld%lld", &m, &n);
for (int i = 1, src; i <= n; i++)
scanf("%lld", &src), adn(sub(i), t, src, 0), adn(t, sub(i), 0, 0);
for (int i = 1; i <= m; i++)
for (int j = 1, srx; j <= n; j++)
{
scanf("%lld", &srx);
if (srx)
adn(bh(i), sub(j), INF, 0), adn(sub(j), bh(i), 0, 0);
}
for (int i = 1, srn; i <= m; i++)
{
adn(s, i, INF, 0);
adn(i, s, 0, 0);
scanf("%lld", &srn);
int srt[50];
srt[0] = 0, srt[srn + 1] = INF;
for (int j = 1; j <= srn; j++)
scanf("%lld", &srt[j]);
for (int j = 1, srx; j <= srn + 1; j++)
scanf("%lld", &srx), adn(i, bh(i), srt[j] - srt[j - 1], srx), adn(bh(i), i, 0, -srx);
}
solve();
printf("%lld", ans);
return 0;
}

/*
2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6
*/

我一定…要…

By Cansult