[CF434D] Nanamis Power Plant

菜爆的我场上只写了暴力qwq

题意

有$ n $个给定二次函数,取值范围$ [l_i,r_i] $,有$ M $个限制条件$ x_u \leq x_v + d $最大化函数值的和。

思路

其实场上是有想到网络流的但是提答太好玩啦而且也没思路

取值范围和函数个数都很小,我们可以考虑把信息建到图上。

从s到t拉n条链表示n个函数。

每条边是取$ x \in [l_i,r_i] $内的值时函数值。

由于求最大值我们对值取负并加个$ inf $。

u和v的限制条件由u的区间向v的可达区间连$ inf $。

Code

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
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <vector>
#include <queue>
typedef long long LL;
#define int LL
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int K = 55,R = 210,base = 100,inf = 0x3f3f3f3f,N = 10010,M = 100010,INF = 2e8;
struct Dinic
{
int head[N],cur[N],d[N],next[M],to[M],cap[M],flow[M],s,t,tot;std::queue<int> Q;
Dinic(int s,int t){this->s = s;this->t = t;init();}inline void init(){tot = -1;memset(head,-1,sizeof(head));memset(flow,0,sizeof(flow));}\
inline void addedge(int u,int v,int w){next[++tot] = head[u];to[tot] = v;cap[tot] = w;head[u] = tot;}
inline void adde(int u,int v,int w){addedge(u,v,w);addedge(v,u,0);}
inline int bfs()
{
memset(d,-1,sizeof(d));
d[s] = 0;Q.push(s);
while(Q.size())
{
int u = Q.front();Q.pop();
for(int i = head[u],v = to[i];~i;v = to[i = next[i]]) if(cap[i] > flow[i] && !~d[v]) {d[v] = d[u] + 1;Q.push(v);}
}
return !!~d[t];
}
inline int dfs(int u,int mf)
{
if(u == t) return mf;
int ret = 0;for(int i = ~cur[u] ? cur[u] : head[u],v = to[i],a;~i;v = to[i = next[i]]) if(cap[i] > flow[i] && d[v] == d[u] + 1 && (a = dfs(v,std::min(cap[i] - flow[i],mf - ret))))
{
ret += a;flow[i] += a;flow[i ^ 1] -= a;cur[u] = i;
if(ret == mf) return ret;
}
cur[u] = 2;return ret;
}
inline int dinic(){int ret = 0;while(bfs()){memset(cur,-1,sizeof(cur));ret += dfs(s,inf);}return ret;}
};
int n,m,s,t;
int a[K],b[K],c[K],f[K][R],mx[K],l[K],r[K];
std::vector<int> pt[K];int cnt = 0;
signed main()
{
n = getint();m = getint();s = ++cnt;t = ++cnt;Dinic D(s,t);
for(int i = 1;i <= n;i++) a[i] = getint(),b[i] = getint(),c[i] = getint();
for(int i = 1;i <= n;i++)
{
l[i] = getint();r[i] = getint();
pt[i].push_back(++cnt);
D.adde(s,cnt,2 * INF);
for(int j = l[i];j <= r[i];j++)
{
int val = a[i] * j * j + b[i] * j + c[i];
D.adde(pt[i].back(),++cnt,INF - val);
pt[i].push_back(cnt);
}
D.adde(cnt,t,2 * INF);
}
for(int mm = 1;mm <= m;mm++)
{
int u = getint(),v = getint(),d = getint();
for(int i = l[v];i <= r[v];i++)
{
int j = i + d;
if(j > r[u]) continue;
D.adde(pt[u][std::max(j - l[u] + 1,0LL)],pt[v][i - l[v] + 1],2 * INF);
}
}
printf("%lld\n",INF * n - D.dinic());
return 0;
}