文章目錄

• 題目描述
• 解析
• 代碼

題目描述

某軟件公司正在規劃一項$n$天的軟件開發計劃，根據開發計劃第$i$天需要$n_i$個軟件開發人員，為了提高軟件開發人員的效率，公司給軟件人員提供了很多的服務，其中一項服務就是要為每個開發人員每天提供一塊消毒毛巾，這種消毒毛巾使用一天后必須再做消毒處理后才能使用。

消毒方式有兩種，A 種方式的消毒需要$a$天時間，B 種方式的消毒需要$b$天，A 種消毒方式的費用為每塊毛巾$f_a$，B 種消毒方式的費用為每塊毛巾$f_b$，而買一塊新毛巾的費用為$f$（新毛巾是已消毒的，當天可以使用）。公司經理正在規劃在這$n$天中，每天買多少塊新毛巾、每天送多少塊毛巾進行 A 種消毒和每天送多少塊毛巾進行 B 種消毒。當然，公司經理希望費用最低。

你的任務就是：為該軟件公司計劃每天買多少塊毛巾、每天多少塊毛巾進行 A 種消毒和多少毛巾進行 B 種消毒，使公司在這項$n$天的軟件開發中，提供毛巾服務的總費用最低。

解析

關鍵是割點的思想
把每天割成早上和晚上兩個點
晚上會得到$n_i$條舊的毛巾
然后按照消毒方式往早上連邊
注意當天的毛巾可以留到第二天

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2300; const int M=2e6+100; const int mod=998244353; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,s,t; struct node{int to,nxt;ll cap,w; }p[M<<1]; int fi[N],cnt,cur[N]; void addline(int x,int y,ll cap,ll w){p[++cnt]=(node){y,fi[x],cap,w};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0,-w};fi[y]=cnt; } ll flow,cost; queue<int>q; ll dis[N]; bool vis[N]; bool spfa(){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push(s);bool flag=0;while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap) continue;if(to==t) flag=1;if(dis[to]>dis[now]+p[i].w){dis[to]=dis[now]+p[i].w;if(!vis[to]){q.push(to);vis[to]=1;}}}}return flag; } ll dfs(int x,ll lim){if(x==t||!lim){cost+=lim*dis[t];return lim;}vis[x]=1;ll res=0;for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]||!p[i].cap||dis[to]!=dis[x]+p[i].w) continue;ll add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(lim) dis[x]=-1;vis[x]=0;return res; } void dinic(){while(spfa()){while(ll tmp=dfs(s,2e18)){flow+=tmp;//printf("tmp=%d\n",tmp);}}return; } int x; int fa,fb,a,b,f; int main(){memset(fi,-1,sizeof(fi));cnt=-1;n=read();a=read();b=read();f=read();fa=read();fb=read();s=n+1;t=s+1;a++;b++;s=n+n+1;t=n+n+2;for(int i=1;i<=n;i++){x=read();addline(s,i+n,x,0);addline(i,t,x,0);}for(int i=1;i<=n;i++) addline(s,i,2e18,f);for(int i=1;i<n;i++) addline(i+n,i+1+n,2e18,0);for(int i=1;i+a<=n;i++) addline(i+n,i+a,2e18,fa);for(int i=1;i+b<=n;i++) addline(i+n,i+b,2e18,fb);dinic();printf("%lld",cost);return 0; }

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P2223：软件开发（费用流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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