<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12

      【CF434D】Nanami's Power Plant 最小割

      【CF434D】Nanami's Power Plant

      題意:有n個二次函數$y=a_ix^2+b_ix+c_i$($a_i,b_i,c_i$是整數),第i個函數要求x的取值在$[l_i,r_i]$之間且為整數。你需要確定每個函數的x的取值,使得所有函數的函數值之和最大。還有m個限制,每條限制形如$u,v,d$,表示$x_u\le x_v+d$。求最大函數值之和。

      $n\le 50,m\le 100,-100\le l_i\le r_i\le 100$

      題解:傻逼了連切糕都忘了。

      對于一個方程,我們把它的所有可能取值按照x從小到大串成一串,首尾分別與S和T相連,其中第i個點和第i+1個點的邊的容量為當$x=l+i-1$時的函數值(由于可能存在負數,我們給每條邊的權值都加上一個大數,最后再把這個大數減去)。對于限制u,v,d,我們從u中所有代表$x_u=i$的點向v中代表$x_v=i-d$的點連一條容量inf的邊,便完成了限制。

       

      #include <cstdio>
      #include <cstring>
      #include <iostream>
      #include <algorithm>
      #include <queue>
      using namespace std;
      typedef long long ll;
      const ll big=1ll<<30;
      const ll inf=1ll<<50;
      int n,m,tot,S,T,cnt;
      ll ans;
      int L[60],R[60],to[200010],nxt[200010],head[12000],d[12000];
      int p[60][210];
      ll val[200010],A[60],B[60],C[60];
      queue<int> q;
      inline void add(int a,int b,ll c)
      {
      	to[cnt]=b,val[cnt]=c,nxt[cnt]=head[a],head[a]=cnt++;
      	to[cnt]=a,val[cnt]=0,nxt[cnt]=head[b],head[b]=cnt++;
      }
      ll dfs(int x,ll mf)
      {
      	if(x==T)	return mf;
      	int i;
      	ll temp=mf,k;
      	for(i=head[x];i!=-1;i=nxt[i])	if(val[i]&&d[to[i]]==d[x]+1)
      	{
      		k=dfs(to[i],min(temp,val[i]));
      		if(!k)	d[to[i]]=-1;
      		temp-=k,val[i]-=k,val[i^1]+=k;
      		if(!temp)	break;
      	}
      	return mf-temp;
      }
      inline int bfs()
      {
      	while(!q.empty())	q.pop();
      	int i,u;
      	memset(d,0,sizeof(d));
      	q.push(S),d[S]=1;
      	while(!q.empty())
      	{
      		u=q.front(),q.pop();
      		for(i=head[u];i!=-1;i=nxt[i])	if(val[i]&&!d[to[i]])
      		{
      			d[to[i]]=d[u]+1;
      			if(to[i]==T)	return 1;
      			q.push(to[i]);
      		}
      	}
      	return 0;
      }
      int main()
      {
      	//freopen("cf434D.in","r",stdin);
      	scanf("%d%d",&n,&m);
      	S=0,T=tot=1;
      	int i,j,a,b,c;
      	memset(head,-1,sizeof(head));
      	for(i=1;i<=n;i++)	scanf("%lld%lld%lld",&A[i],&B[i],&C[i]);
      	for(i=1;i<=n;i++)
      	{
      		scanf("%d%d",&L[i],&R[i]);
      		add(S,tot+1,inf);
      		for(j=L[i];j<=R[i];j++)
      		{
      			p[i][j-L[i]]=++tot;
      			add(tot,tot+1,big-(A[i]*j*j+B[i]*j+C[i]));
      		}
      		p[i][R[i]-L[i]+1]=++tot;
      		add(tot,T,inf);
      	}
      	for(i=1;i<=m;i++)
      	{
      		scanf("%d%d%d",&a,&b,&c);
      		for(j=max(L[b],L[a]-c);j<=min(R[b],R[a]-c)+1;j++)
      		{
      			add(p[a][j+c-L[a]],p[b][j-L[b]],inf);
      		}
      	}
      	while(bfs())	ans+=dfs(S,inf);
      	printf("%lld",big*n-ans);
      	return 0;
      }

       

      posted @ 2018-04-05 17:23  CQzhangyu  閱讀(538)  評論(0)    收藏  舉報
      主站蜘蛛池模板: 亚洲一区久久蜜臀av| 香港日本三级亚洲三级| 欧美男男作爱videos可播放| 国产中文字幕精品免费| 亚洲最大国产成人综合网站| 国产精品人成视频免| 亚洲国产另类久久久精品| 欧美牲交a欧美牲交aⅴ一| 九九在线精品国产| 夜夜躁狠狠躁日日躁| 不卡在线一区二区三区视频| bt天堂新版中文在线| 久久丁香五月天综合网| 少妇高潮喷水惨叫久久久久电影 | 午夜福利在线永久视频| 夜夜躁狠狠躁日日躁| 亚洲av乱码一区二区| 在线一区二区中文字幕| 午夜福利看片在线观看| 人妻无码| 亚洲69视频| 人妻少妇久久中文字幕| 久久在线视频免费观看| 日韩内射美女人妻一区二区三区| 国产午夜福利在线观看播放| 亚洲天堂视频网| 国产精品成人av电影不卡| 97视频精品全国免费观看| 国产欧美va欧美va在线| 国产精品一区 在线播放| 亚洲无人区视频在线观看| 国内精品久久久久影院日本| 国产亚洲精品久久综合阿香| 亚洲国产一区二区三区久| 婷婷丁香五月激情综合| 日韩精品一区二区三区激情视频 | 久久久久无码精品国产h动漫| 国产成人亚洲欧美二区综合| 喀喇沁旗| 色老99久久精品偷偷鲁| 国产日韩久久免费影院|