正題

題目鏈接:https://www.luogu.com.cn/problem/P1251

---

題目大意

$N$天，第$i$天需要$a_i$個餐巾。

每個餐巾價格為$p$，使用完后有兩種清洗方法

清洗$m$天，費用為$f$

清洗$n$天，費用為$s$

求滿足所有需求的最小花費

$1\le N\le 2000,1\le a_i\le 10^7,1\le p,f,s\le 10^4$

---

解題思路

網絡流$24$題里的題目。而且顯然是費用流

毛巾使用過后還可以再使用，我們有兩種方法來限制這個條件

不使用最大流限制，那么我們每次使用毛巾可以視為流過一條流量為$?inf$的邊，這樣為了最小費用顯然會滿足所有條件。最后將流過的$?inf$的權值加回去就好了

使用最大流來限制。可以發現因為毛巾的條件是必須滿足的，所以我們可以默認每次使用完后一定會剩下$a_i$個毛巾，所以我們直接讓流量表示毛巾，然后每次多產生回$a_i$流量就好了

第二種好寫一點，這里用的也是第二種

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=4100,inf=1e18; struct node{ll to,next,w,c; }a[N<<4]; ll n,A,B,F,fa,fb,tot,ans,s,t; ll ls[N],f[N],mf[N],pre[N],w[N]; bool v[N];queue<int> q; void addl(ll x,ll y,ll w,ll c){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c;return; } bool SPFA(){memset(f,0x3f,sizeof(f));f[s]=0;mf[s]=inf;q.push(s);v[s]=1;while(!q.empty()){ll x=q.front();q.pop();v[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(a[i].w&&f[x]+a[i].c<f[y]){f[y]=f[x]+a[i].c;pre[y]=i;mf[y]=min(mf[x],a[i].w);if(!v[y])v[y]=1,q.push(y);}}}return f[t]<inf; } void Updata(){ll x=t;ans+=mf[x]*f[x];while(x!=s){a[pre[x]].w-=mf[t];a[pre[x]^1].w+=mf[t];x=a[pre[x]^1].to;}return; } signed main() {scanf("%lld",&n);s=2*n+1;t=s+1;tot=1;scanf("%lld%lld%lld%lld%lld",&A,&B,&F,&fa,&fb);for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);for(ll i=1;i<=n;i++){addl(s,i,inf,F);addl(i,t,w[i],0);addl(s,i+n,w[i],0);if(i+A+1<=n)addl(i+n,i+A+1,inf,fa);if(i+B+1<=n)addl(i+n,i+B+1,inf,fb);if(i<n)addl(i,i+1,inf,0);}while(SPFA())Updata();printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的P1251-餐巾计划问题【费用流】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。