感觉和刚刚做过一场模拟赛的一道题很类似……
考虑网络流，对每个函数都建立 [li,ri] 的点，点 (i,j) 表示函数 fi 当xi=j时的点。
我们考虑最小损失。设一个极大值 lim（大于所有的fi(x)），将也就是要求lim−fi(x) 的最小值。
我们从点 (i,j) 向点 (i,j+1)（如果j=ri 那就是超汇 T）流lim−fi(j)，从超源S 向点 (i,li) 流∞。
大概就是这样一张图：
如果这些函数的取值互补干涉，那么 n×lim− 最小割 就是答案。
我们考虑如何加入这些限制。
如果现在有限制 xu≤xv+d，也就是xv≥xu−d。如果我们割了xu 这条边，在 v 这条链上我们只能割 xu−d 以后的边。那就不妨从 u 这条表上所有的 x 向v这条边上所有的 x−d 连一条 ∞ 的边。
如果割绿色的那两条边：
很开心地测一下样例，炸了……
我们来看这种情形（对样例 1 略有改动）：
1
2
3
4
5
6
7
| 2 2
0 1 0
0 1 1
2 3
1 2
1 2 0
2 1 0
|
建出来的图大概是长这样的：
最小割是选 (1,3)→T 和(2,3)→T。
但显然 (1,3)→T 是不能选的。因为由 x1≤x2 和x2≤x1可知x1=x2。
于是我们只得再建一个 (i,ri+1) 点，(i,ri)→(i,ri+1)流 fi(ri)，(i,ri+1)→T 流∞。
这样就完美了。
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL maxn = 10005;
const LL maxm = 5000005;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const LL lim = 1000000000000;
struct Edge
{
LL to, nxt, cap;
} e[maxm << 1];
LL first[maxn], first_bak[maxn];
inline void add_edge(LL from, LL to, LL cap)
{
static LL cnt = -1;
e[++cnt].nxt = first[from];
first[from] = cnt;
e[cnt].to = to;
e[cnt].cap = cap;
e[++cnt].nxt = first[to];
first[to] = cnt;
e[cnt].to = from;
e[cnt].cap = 0;
}
LL n, m, S, T;
LL bh[105][205];
LL a[maxn], b[maxn], c[maxn];
LL ll[maxn];
LL rr[maxn];
LL dep[maxn];
inline LL getans(LL I, LL x)
{
return a[I] * x * x + b[I] * x + c[I];
}
inline bool bfs()
{
memset(dep, 0x3f, sizeof(dep));
queue<LL> q;
q.push(S);
dep[S] = 0;
for(int i = S; i <= T; ++i)
first[i] = first_bak[i];
while(!q.empty())
{
LL now = q.front();
q.pop();
for(int i = first[now]; ~i; i = e[i].nxt)
{
LL to = e[i].to;
if(dep[to] >= inf && e[i].cap > 0)
{
dep[to] = dep[now] + 1;
q.push(to);
}
}
}
return dep[T] < inf;
}
inline LL dfs(LL now, LL lim)
{
if(!lim || now == T)
return lim;
LL flow = 0;
for(int i = first[now]; ~i; i = e[i].nxt)
{
first[now] = i;
register LL to = e[i].to, f;
if(dep[to] == dep[now] + 1 && (f = dfs(to, min(lim, e[i].cap))) > 0)
{
lim -= f;
flow += f;
e[i].cap -= f;
e[i ^ 1].cap += f;
if(lim <= 0)
break;
}
}
return flow;
}
inline LL dinic()
{
LL flow = 0;
while(bfs())
flow += dfs(S, inf);
return flow;
}
int main()
{
memset(first, 0xff, sizeof(first));
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
for(int i = 1; i <= n; ++i)
{
scanf("%lld%lld", &ll[i], &rr[i]);
add_edge(S, T + 1, inf);
for(LL j = ll[i] + 100; j <= rr[i] + 101; ++j)
{
bh[i][j] = ++T;
if(j != ll[i] + 100)
add_edge(bh[i][j - 1], bh[i][j], lim - getans(i, j - 1 - 100));
}
}
T++;
for(LL i = 1; i <= n; ++i)
add_edge(bh[i][rr[i] + 101], T, inf);
for(int i = 1, u, v, d; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &d);
for(int j = ll[u]; j <= rr[u] + 1; ++j)
if(ll[v] <= j - d && j - d <= rr[v] + 1)
add_edge(bh[u][j + 100], bh[v][j - d + 100], inf);
}
for(int i = S; i <= T; ++i)
first_bak[i] = first[i];
printf("%lld\n", n * lim - dinic());
return 0;
}
|
