[CF434D]Nanami's Power Plant

题目大意：

\(N\)个二次函数\(f_i(x)=a_ix^2+b_ix+c_i(l_i\le x\le r_i)\)，\(M\)个约束条件\((u,v,d)\)，表示\(x_u\le 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 \neq 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\to node(i,l_i-1)\)，容量为\(\infty\)。

对于所有的\(node(i,r_i)\)，连边\(s\to node(i,r_i)\)，容量为\(\infty\)。

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

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

答案即为\(lim\times n-maxflow\)。

源代码：

#include#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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
          
            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
           
             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

转载于:https://www.cnblogs.com/skylee03/p/9368191.html

你可能感兴趣的文章