最大值

小鱼儿 2021-09-30 00:40 371阅读 0赞

# 最大值 #

#### 时间限制: 3000 ms 内存限制: 131072 KB ####

### 题目描述 ###

Shy 有 n 个发电站。每个发电站有一个 level（可正可负的整数），i 号发电站的 level要在 l\[i\],r\[i\]之间（包含），Level x 会带来 fi(x)的发电量。  
Shy 还有 m 个限制。限制是这样的形式，x\[u\]≤x\[v\]+d，表示 u 的 level 小于等于 v 的level 加 d（d 是整数）。  
请问最大发电量是多少。

### 输入 ###

第一行两个整数 n，m 表示发电站的数目和限制的数目；  
接下来 n 行，每行三个整数 ai,bi,ci 表示 fi,fi(x)=ai*x*x+bi\*x+ci；  
接下来 n 行每行两个整数 l\[i\],r\[i\]；  
接下来 m 行，每行三个整数 u，v，d，表示 x\[u\]≤x\[v\]+d。

### 输出 ###

一个正整数表示答案。

### 输入样例 ###

5 8  
1 -8 20  
2 -4 0  
\-1 10 -10  
0 1 0  
0 -1 1  
1 9  
1 4  
0 10  
3 11  
7 9  
2 1 3  
1 2 3  
2 3 3  
3 2 3  
3 4 3  
4 3 3  
4 5 3  
5 4 3

### 输出样例 ###

### 数据规模 ###

对于 30%的数据，1≤n≤3；  
对于 100%的数据，1≤n≤50,0≤m≤100,|ai|≤10,|bi|≤1000,|ci|≤1000, -100≤|li|≤|ri|≤100，1≤u，v≤n，u≠v，|di|≤200。

网络流。  
水博客原因如数学一题。。。不累述。  
你需要学会当前弧优化，不然卡死你（90分）

#include<bits/stdc++.h> using namespace std; const int maxn = 100010, s = 0, t = 100005, INF = 0x3f3f3f3f; struct lpl{ int to, dis; }lin; queue<int> q; vector<lpl> edge; vector<int> point[maxn]; int layer[maxn], itr[maxn]; int n, m, cnt = -1, ans, a[105], b[105], c[105], l[105], r[105], u[105], v[105], d[105]; inline void putit() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i], &b[i], &c[i]); for(int i = 1; i <= n; ++i) scanf("%d%d", &l[i], &r[i]); for(int i = 1; i <= m; ++i) scanf("%d%d%d", &u[i], &v[i], &d[i]); } inline void connect(int A, int B, int D) { cnt++; lin.to = B; lin.dis = D; edge.push_back(lin); point[A].push_back(cnt); cnt++; lin.to = A; lin.dis = 0; edge.push_back(lin); point[B].push_back(cnt); } inline int calc(int t, int now) { return a[t] * now * now + b[t] * now + c[t]; } inline int id(int data, int line) { int ret = (line - 1) * 201; ret += (data - l[line] + 1); return ret; } inline void prepare() { for(int i = 1; i <= n; ++i){ connect(s, (i - 1) * 201 + 1, INF); int p = 1; for(int j = l[i]; j < r[i]; ++j){ connect((i - 1) * 201 + p, (i - 1) * 201 + p + 1, 0 - calc(i, j) + 10000005); p++; } connect((i - 1) * 201 + p, t, 0 - calc(i, r[i]) + 10000005); } int beg, en, now; for(int i = 1; i <= m; ++i){ beg = l[v[i]]; en = r[v[i]]; for(int j = beg; j <= en; ++j){ now = j + d[i]; if(now >= r[u[i]]) break; if(j == en) {connect(id(now, u[i]) + 1, t, INF); break;} connect(id(now, u[i]) + 1, id(j, v[i]) + 1, INF); } } } inline bool bfs() { memset(itr, 0, sizeof(itr)); memset(layer, 0, sizeof(layer)); q.push(s); layer[s] = 1; while(!q.empty()){ int now = q.front(); q.pop(); for(int i = point[now].size() - 1; i >= 0; --i){ int qwe = point[now][i]; if(edge[qwe].dis <= 0 || layer[edge[qwe].to] != 0) continue; layer[edge[qwe].to] = layer[now] + 1; q.push(edge[qwe].to); } } return layer[t]; } inline int dfs(int a, int w) { if(a == t || w == 0) return w; int ret = 0, llppdd = point[a].size() - 1; for(int i = itr[a]; i <= llppdd; ++i){ int now = point[a][i]; if(layer[edge[now].to] != layer[a] + 1 || edge[now].dis <= 0) continue; int tmp = dfs(edge[now].to, min(w, edge[now].dis)); edge[now].dis -= tmp; edge[now ^ 1].dis += tmp; w -= tmp; ret += tmp; itr[a] = i; if(!w) break; } return ret; } inline void Dinic() { while(bfs()) ans += dfs(s, INF); printf("%d", n * 10000005 - ans); } int main() { putit(); prepare(); Dinic(); return 0; }

转载于:https://www.cnblogs.com/LLppdd/p/8946832.html