| 记录编号 |
319699 |
评测结果 |
AAAAAAAAAAAA |
| 题目名称 |
[网络流24题] 餐巾 |
最终得分 |
100 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.104 s |
| 提交时间 |
2016-10-10 21:42:10 |
内存使用 |
57.63 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define LL long long
#define INF ((~(1<<31))>>1)
using namespace std;
const int maxn=2050<<1;
struct edge{int to,cap,prev;LL cost;}e[3000010];
void addedge(int,int,int,LL);
void insert(int,int,int,LL);
void mincostflow();
void SPFA();
int dfs(int,int);
int last[maxn],len=0,now[maxn];
bool inq[maxn];
int n,a,b,s,t;
LL ca,cb,cc,c[maxn],dis[maxn],ans=0ll;
int main(){
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
memset(last,-1,sizeof(last));
scanf("%d",&n);
a++;b++;
s=(n<<1|1);t=s+1;
for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
scanf("%lld%d%lld%d%lld",&cc,&a,&ca,&b,&cb);
for(int i=1;i<=n;i++){
ans+=c[i]*INF;
addedge(s,i,INF,cc);
addedge(i,i+n,c[i],-INF);
if(i<n)addedge(i+n,i+n+1,INF,0);
if(i+a<=n)addedge(i+n,i+a,INF,ca);
if(i+b<=n)addedge(i+n,i+b,INF,cb);
}
t=n+n;
mincostflow();
printf("%lld",ans);
/*printf("\n");
for(int i=last[s];i!=-1;i=e[i].prev)printf("day %d buys %d\n",e[i].to,INF-e[i].cap);
for(int i=1;i<n;i++)for(int j=last[i+n];j!=-1;j=e[j].prev)if(e[j].to==i+a)printf("day %d maintain a %d\n",i,INF-e[j].cap);
for(int i=1;i<n;i++)for(int j=last[i+n];j!=-1;j=e[j].prev)if(e[j].to==i+b)printf("day %d maintain b %d\n",i,INF-e[j].cap);*/
fclose(stdin);
fclose(stdout);
return 0;
}
void addedge(int x,int y,int z,LL w){
//printf("addedge(%d,%d,%d,%lld)\n",x,y,z,w);
insert(x,y,z,w);
insert(y,x,0,-w);
}
void insert(int x,int y,int z,LL w){
e[len].to=y;
e[len].cap=z;
e[len].cost=w;
e[len].prev=last[x];
last[x]=len++;
}
void mincostflow(){
//int flow=0;
for(;;){
SPFA();
if(dis[t]>=0ll)break;
memset(now,0,sizeof(now));
/*flow+=*/dfs(s,INF);
//printf("ans=%lld\n",ans%INF);
}
//printf("flow=%d\n",flow);
}
void SPFA(){
int x;
memset(inq,0,sizeof(inq));
memset(dis,63,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty()){
x=q.front();
q.pop();
inq[x]=false;
for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&dis[e[i].to]>dis[x]+e[i].cost){
dis[e[i].to]=dis[x]+e[i].cost;
if(!inq[e[i].to]){
inq[e[i].to]=true;
q.push(e[i].to);
}
}
}
//for(int i=1;i<=n+n+1;i++)printf("%lld ",dis[i]);printf("\n");
}
int dfs(int x,int delta){
//printf("dfs(%d,%d)\n",x,delta);
if(x==t||!delta)return delta;
int f;
for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-1;i=e[i].prev)if(e[i].cap>0&&dis[e[i].to]==dis[x]+e[i].cost){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^1].cap+=f;
ans+=e[i].cost*(LL)f;
return f;
}
return 0;
}
/*
4 1 2 3 2 1
8 2 1 6
Answer:
38
*/
/*
4 0 1 5 3 1
7 6 2 3
Answer:
60
*/
/*
又见神の脑洞...
我们把每天看做一个点，那么问题可以转化为带下限的最小费用流。
下限直接把节点内部的边的费用设为-INF，再添一条费用为0容量为+INF的边，
这样再增广之后可以保证一定是满足下限的最小费用流。
最后的费用加上那些负无穷扣回去的费用即可。
顺便一提，由构图方法可知没有负环，所以SPFA大可不加判负环。
好吧那条节点内部容量正无穷的边用不着...
因为第一天肯定不会多买，每一天不用的渔船会通过到下一天晚上的边流到下一天
(而不会走去下一天早上的边使得明天的渔船太多)。
*/