首页 > 代码库 > cf 434d Nanami's Power Plant 网络流

cf 434d Nanami's Power Plant 网络流

2024-07-11 16:18:32   219人阅读

题目大意就是有n个发电机，每个发电机有l到r个档位可供选择，每个档位的输出功率是已知的，另外还有一些限制条件，形式为xu ≤ xv + d，表示发电机u的档位要小于v的档位加d，d是一个已知的整数。求n个发电机的最大功率。

假设没有最后那个限制条件，那么对于每个发电机i拆点成l-1，l。。。到r相邻两档位连边为max-f(i)，f(i)是档位i的输出功率，max是一个大数，大于等于所有档位的输出功率。l-1与源点连inf的边，r与汇点连inf的边。假设最大流为flow，那么max*n-flow就是答案。

然后考虑这些限制条件，对于每个条件xu ≤ xv + d，对于u的每个拆点x，连接 ( u , x ) 到 ( v , x - d )容量为inf的边，此时的max*n-flow就是答案。

然后为什么这样就会满足限制呢，因为假设不满足，此时在残余网络中又会出现一条增广路，直到满足条件为止。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int maxn=15000;#define inf 1<<30int level[maxn],que[maxn];int head[maxn],lon;int aa[70],bb[70],cc[70];int l[70],r[70];int start[70];struct edge{    int next,to,c;}e[500000];void edgeini(){    memset(head,-1,sizeof(head));    lon=-1;}void edgemake(int from,int to,int c){    e[++lon].c=c;    e[lon].to=to;    e[lon].next=head[from];    head[from]=lon;}void make(int from,int to,int c){    edgemake(from,to,c);    edgemake(to,from,0);}bool makelevel(int s,int t){    memset(level,0,sizeof(level));    int front=1,end=0;    que[++end]=s;    level[s]=1;    while(front<=end)    {        int u=que[front++];        if(u==t) return true;        for(int k=head[u];k!=-1;k=e[k].next)        {            int v=e[k].to;            if(!level[v]&&e[k].c)            {                que[++end]=v;                level[v]=level[u]+1;            }        }    }    return false;}int dfs(int now,int t,int maxf){    if(now==t||maxf==0) return maxf;    int ret=0;    for(int k=head[now];k!=-1;k=e[k].next)    {        int u=e[k].to;        if(level[u]==level[now]+1&&e[k].c)        {            int f=dfs(u,t,min(e[k].c,maxf-ret));            e[k].c-=f;            e[k^1].c+=f;            ret+=f;            if(ret==maxf) return ret;        }    }    if(ret==0) level[now]=0;    return ret;}int maxflow(int s,int t){    int ret=0;    while(makelevel(s,t))    {        ret+=dfs(s,t,inf);    }    return ret;}int fun(int p,int x){    return aa[p]*x*x+bb[p]*x+cc[p];}int id(int p,int x){    return start[p]+x-l[p];}int main(){    int n,m;    int i,j;    scanf("%d%d",&n,&m);    edgeini();    int MAX=-inf;    int cnt=0;    for(i=1;i<=n;i++)        scanf("%d%d%d",&aa[i],&bb[i],&cc[i]);    for(i=1;i<=n;i++)    {        scanf("%d%d",&l[i],&r[i]);        start[i]=cnt+1;        cnt=cnt+r[i]-l[i]+2;        for(j=l[i];j<=r[i];j++)            MAX=max(MAX,fun(i,j));    }    for(i=1;i<=n;i++)    {        make(0,start[i],inf);        for(j=l[i];j<=r[i];j++)            make(id(i,j),id(i,j+1),MAX-fun(i,j));        make(id(i,r[i]+1),cnt+1,inf);    }    int u,v,d;    while(m--)    {        scanf("%d%d%d",&u,&v,&d);        for(i=l[u];i<=r[u];i++)        {            if(i-d>=l[v]&&i-d<=r[v]+1)                make(id(u,i),id(v,i-d),inf);        }    }    int ans=maxflow(0,cnt+1);    printf("%d\n",MAX*n-ans);    return 0;}
View Code

 


联系
我们