首页 > 代码库 > COGS461. [网络流24题] 餐巾
COGS461. [网络流24题] 餐巾
【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
(1)购买新的餐巾，每块需p分；
(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。
【输出】
一行，最小的费用
【样例】
napkin.in
3
3 2 4
10 1 6 2 3
napkin.out
64
【数据规模】
n<=200,Ri<=50
虽然写完了，但是不太会解释。
题解出门左转hzwer神犇的博客
1 #include<iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<algorithm> 6 #include<queue> 7 #define LL long long 8 using namespace std; 9 const int INF=1e9;10 const int mxn=210*2;11 inline int read(){12 int sum=0,flag=1;char ch=getchar();13 while(ch!=‘-‘&&(ch>‘9‘||ch<‘0‘))ch=getchar();14 if(ch==‘-‘){flag=-1;ch=getchar();}15 while(ch<=‘9‘&&ch>=‘0‘){sum=sum*10+ch-‘0‘;ch=getchar();}16 return sum*flag;17 }18 struct edge{19 int u,v,nxt,f,w;20 }e[mxn*mxn*2];21 int hd[mxn],mct=1;22 void add_edge(int u,int v,int c,int w){23 e[++mct].u=u;e[mct].v=v;e[mct].nxt=hd[u];e[mct].f=c;e[mct].w=w;hd[u]=mct;return;24 }25 void insert(int u,int v,int c,int w){26 add_edge(u,v,c,w);add_edge(v,u,0,-w);return;27 }28 int N,p,n,m,S,T;29 int a,f,s;30 int dis[mxn];31 int pre[mxn];32 bool inq[mxn];33 bool SPFA(){34 memset(dis,0x3f,sizeof dis);35 queue<int>q;36 q.push(S);37 dis[S]=0;38 while(!q.empty()){39 int u=q.front();q.pop();inq[u]=0;40 for(int i=hd[u];i;i=e[i].nxt){41 int v=e[i].v;42 if(e[i].f>0 && dis[v]>dis[u]+e[i].w){43 dis[v]=dis[u]+e[i].w;44 pre[v]=i;45 if(!inq[v]){46 inq[v]=1;47 q.push(v);48 }49 }50 }51 }52 if(dis[T]!=0x3f3f3f3f)return 1;53 return 0;54 }55 int solve(){56 int tmp=0x3f3f3f3f,res=0;57 while(SPFA()){58 tmp=0x3f3f3f3f;59 for(int i=pre[T];i>1;i=pre[e[i].u]){60 tmp=min(tmp,e[i].f);61 }62 for(int i=pre[T];i>1;i=pre[e[i].u]){63 e[i].f-=tmp;64 e[i^1].f+=tmp;65 res+=tmp*e[i].w;66 }67 }68 return res;69 }70 int main(){71 freopen("napkin.in","r",stdin);72 freopen("napkin.out","w",stdout);73 int i,j;74 N=read();75 S=0;T=N*2+1;76 for(i=1;i<=N;i++){77 a=read();78 insert(S,i,a,0);79 insert(i+N,T,a,0);80 }81 p=read();m=read();f=read();n=read();s=read();82 for(i=1;i<=N;i++){83 if(i+1<=N)insert(i,i+1,INF,0);84 if(i+m<=N)insert(i,i+m+N,INF,f);85 if(i+n<=N)insert(i,i+n+N,INF,s);86 insert(S,i+N,INF,p);//购买87 }88 int ans=solve();89 printf("%d\n",ans);90 return 0;91 }
COGS461. [网络流24题] 餐巾
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。