[CF434D]Nanami's Power Plant

摘要:
[CF434D]Nanami的PowerPlant主题的主要思想:二次函数、约束、表示。请最大化,其中是整数。对于的数据,请确保所有数字都是整数。总的来说,容量是。用于表示足够大的数字。对于每个二次函数中的所有连接边,容量为。
[CF434D]Nanami's Power Plant

题目大意:

(N)个二次函数(f_i(x)=a_ix^2+b_ix+c_i(l_ile xle r_i))(M)个约束条件((u,v,d)),表示(x_ule x_v+d)。请最大化(sum_{i=1}^nf_i(x_i)),其中(x_i)是整数。

对于(100\%)的数据,(1 leq N leq 50 , 0 leq M leq 100 , |a_i| leq 10 , |b_i| , |c_i| leq 1000 , −100 leq l_i leq r_i leq 100 , 1 leq u , v leq N , u eq v , |d| leq 200),保证所有数均为整数。

思路:

将每个二次函数(i)拆成(node(i,l_i-1)sim node(i,r_i))(r_i-l_i+2)个点。

对于所有的(node(i,l_i-1)),连边(s o node(i,l_i-1)),容量为(infty)

对于所有的(node(i,r_i)),连边(s o node(i,r_i)),容量为(infty)

(lim)表示一个足够大的数,对于每个二次函数(i)中所有的(node(i,j)),连边(node(i,j-1) o node(i,j)),容量为(lim-f_i(j))

考虑约束条件((u,v,d)),连边(node(u,j) o node(v,j−d)),容量为(infty)

答案即为(lim imes n-maxflow)

源代码:

#include<map>
#include<queue>
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
inline int getint() {
	register char ch;
	register bool neg=false;
	while(!isdigit(ch=getchar())) neg|=ch=='-';
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return neg?-x:x;
}
const int N=51,V=1e4+1,E=1e5+1;
struct Edge {
	int from,to,remain,next;
};
Edge e[E];
int h[V],sz,cnt;
inline void add_edge(const int &u,const int &v,const int &w) {
	e[sz]=(Edge){u,v,w,h[u]};h[u]=sz++;
	e[sz]=(Edge){v,u,0,h[v]};h[v]=sz++;
}
struct Func {
	int a,b,c;
	int operator () (const int &x) const {
		return a*x*x+b*x+c;
	}
};
Func f[N];
int l[N],r[N];
int lev[V],s,t,cur[V];
inline void bfs() {
	memset(lev,-1,sizeof lev);
	lev[s]=0;
	std::queue<int> q;
	q.push(s);
	while(!q.empty()) {
		const int &x=q.front();
		for(register int i=h[x];~i;i=e[i].next) {
			const int &y=e[i].to,&r=e[i].remain;
			if(r&&!~lev[y]) {
				lev[y]=lev[x]+1;
				q.push(y);
			}
		}
		q.pop();
	}
}
int dfs(const int &x,const int &flow) {
	if(x==t) return flow;
	for(int &i=cur[x];~i;i=e[i].next) {
		const int &y=e[i].to;
		if(e[i].remain&&lev[y]>lev[x]) {
			if(int d=dfs(y,std::min(flow,e[i].remain))) {
				e[i].remain-=d;
				e[i^1].remain+=d;
				return d;
			}
		}
	}
	return 0;
}
inline int dinic() {
	int maxflow=0;
	for(;;) {
		bfs();
		if(!~lev[t]) break;
		memcpy(cur,h,sizeof h);
		while(int flow=dfs(s,INT_MAX)) {
			maxflow+=flow;
		}
	}
	return maxflow;
}
std::map<int,int> node[N];
int main() {
	memset(h,-1,sizeof h);
	const int n=getint(),m=getint();
	for(register int i=1;i<=n;i++) {
		const int a=getint(),b=getint(),c=getint();
		f[i]=(Func){a,b,c};
	}cnt=1;
	s=cnt++;
	for(register int i=1;i<=n;i++) {
		l[i]=getint(),r[i]=getint();
		for(register int j=l[i]-1;j<=r[i];j++) {
			node[i][j]=cnt++;
		}
	}
	const int M=INT_MAX/n;
	for(register int i=1;i<=n;i++) {
		add_edge(s,node[i][l[i]-1],INT_MAX);
		for(register int j=l[i];j<=r[i];j++) {
			add_edge(node[i][j-1],node[i][j],M-f[i](j));
		}
		add_edge(node[i][r[i]],t,INT_MAX);
	}
	for(register int i=0;i<m;i++) {
		const int u=getint(),v=getint(),d=getint();
		for(register int j=std::max(l[u],l[v]+d)-1;j<=std::min(r[u],r[v]+d);j++) {
			add_edge(node[u][j],node[v][j-d],INT_MAX);
		}
	}
	printf("%d
",M*n-dinic());
	return 0;
}

免责声明:文章转载自《[CF434D]Nanami's Power Plant》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[TC6194]AllWoundUp[HZOI 2016]我们爱数数下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

ExtJS4.x treegrid 控件复选框的研究

1 treegrid 简介 最近在研究ExtJS4.x版本,官方在发布包中包含了一个treegrid插件,先看下效果: 本人想在Controller中动态获取、设置左侧的复选框列。 这里是官方提供的示例:http://www.ostools.net/uploads/apidocs/extjs4.1/examples/tree/treegrid.html 这...

jquery实战视频教程_选项卡效果一

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> &l...

创建第一个Symfony工程

我们的第一个Symfory工程 现在我们试验一下Symfony。我们要在一个小时内构建一个全功能的网络程序。一个书店销售程序?可以!一个Weblog!这是一个好主意。让我们开始吧。安装Symfony并且初始化工程为了方便,我们将会使用Symfony沙盒。这是一个空的Symfony工程,在其中已经包含了所有所需要的库,并且完成了基本的配置。比起其他类型的安装...

分布式事务 dtc 的使用

利用分布式的函数 OpenDataSource OpenQuery OpenRowSet 处理分布式数据库,写程序比较简单,但配置DTC比较复杂,查了MSDN为证。 本人为了简单也写了相应的程序,发觉10个公司只有一个公司能得到数据。搜了MSDN,发觉原来有那么多人在配置DTC上碰到问题。 研究了文章如下 一.A.不用事务,关用SELECT 语句.是否可以...

请问一下哪有机械键盘的实体店可以体验一下? 外设 Chiphell 分享与交流用户体验的最佳平台 Powered by Discuz!

请问一下哪有机械键盘的实体店可以体验一下? - 外设 - Chiphell - 分享与交流用户体验的最佳平台 - Powered by Discuz! [键盘]请问一下哪有机械键盘的实体店可以体验一下?[复制链接] stavent stavent当前离线 天使 天使, 积分 204, 距离下一级还需 296...

XML简介

针对于不同平台,不同语言之间的数据共享,目前使用最多的技术是XML和JSON。刚做开发不久,根据自己的理解总结一下XML技术。 一.XML概念 XML英文全称为Extensible Markup Language,可扩展标记语言。主要用于保存和处理数据同时,保存和处理数据之间的关系。XML的实质是一段字符串,根据这一特点,XML具有跨平台,跨语言特性。 二....