1 条题解
-
1
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ano ((i-1)^1)+1 using namespace std; const int INF=0x7f7f7f7f,N=2e3+100,M=6e3+100; int n,a,b,f,fa,fb,tot,ans,s,t; int head[N],ver[2*M],edge[2*M],Next[2*M],cost[2*M]; int pre[N],minf[N],d[N]; bool v[N]; void add(int x,int y,int z,int c) { ver[++tot]=y,edge[tot]=z,cost[tot]=c,Next[tot]=head[x],head[x]=tot; ver[++tot]=x,edge[tot]=0,cost[tot]=-c,Next[tot]=head[y],head[y]=tot; }//网络流双向建边 bool spfa() { memset(v,0,sizeof(v)); memset(d,0x7f,sizeof(d)); queue<int> q; d[s]=0,v[s]=1,minf[s]=INF; q.push(s); while(q.size()) { int x=q.front();q.pop();v[x]=0; for(int i=head[x];i;i=Next[i]) if(edge[i]) { int y=ver[i]; if(d[x]+cost[i]<d[y]) { d[y]=d[x]+cost[i]; minf[y]=min(minf[x],edge[i]); pre[y]=i; if(!v[y]) { q.push(y); v[y]=1; } } } } return d[t]!=INF; } void update() { int x=t; while(x!=s) { int i=pre[x]; edge[i]-=minf[t]; edge[ano]+=minf[t]; x=ver[ano]; } ans+=d[t]*minf[t]; }//最小费用最大流模板 int main() { scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb); t=2*n+1,a++,b++;//也可以先将a,b分别加1,后面就不用加1 for(int i=1;i<=n;i++) { int x; scanf("%d",&x); add(s,i+n,x,0),add(i,t,x,0),add(s,i,INF,f);//1,2,3操作 if(i+a<=n) add(i+n,i+a,INF,fa);//4操作 if(i+b<=n) add(i+n,i+b,INF,fb);//5操作 if(i+1<=n) add(i,i+1,INF,0);//6操作,这里是从每天早上向第二天早上连边 } while(spfa()) update();//跑最小费用最大流。 printf("%d",ans); return 0; }
- 1
信息
- ID
- 1221
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 7
- 已通过
- 6
- 上传者