最大值
最大值
时间限制: 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)=aixx+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
输出样例
46
数据规模
对于 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;
}
1、[转]IT开发工程师的悲哀
2、Masonry的使用
3、mysql和java 中关于时间的处理详解
4、BZOJ4820 [SDOI2017]硬币游戏
5、BZOJ_2002