最小費用最大流

/**************************************************************Problem: 1221User: lxy8584099Language: C++Result: AcceptedTime:1544 msMemory:1532 kb ****************************************************************//*最小費用最大流st->第i天白天 needi流 0 （可能消毒利用的第i天白天->第i+1天白天 無限流 0費用 （臟的留在下一天第i天白天->第i+a+1天晚上 inf流 fa費用 （A方式消毒第i天白天->第i+b+1天晚上 inf流 fb費用 （B方式消毒 以上處理消毒用st->第i天晚上 inf流 f費用 （直接使用購買的第i天晚上->ed needi流 0費用 */ #include<queue> #include<cstdio> #include<cstring> #define inf (0x3fffffff) using namespace std; const int N=2050; struct pp {int v,nxt,d,c;} e[N*20]; int head[N],tot=1,st,ed,n,a,b,f,fa,fb,nd[N>>1]; int from[N],flow[N],dis[N],res; bool vis[N]; void add(int u,int v,int d,int c) {e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;e[tot].d=d,e[tot].c=c;e[++tot].nxt=head[v];head[v]=tot;e[tot].v=u;e[tot].d=-d,e[tot].c=0; } int min(int a,int b){return a>b?b:a;} bool spfa() {memset(flow,0,sizeof(flow)); flow[st]=inf;memset(dis,0x3f,sizeof(dis)); dis[st]=0;queue < int > q; q.push(st);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int j=head[u];j;j=e[j].nxt){int v=e[j].v,d=e[j].d,c=e[j].c;if(c<=0) continue;if(dis[v]>dis[u]+d){dis[v]=dis[u]+d,from[v]=j;flow[v]=min(flow[u],c);if(!vis[v]) vis[v]=1,q.push(v);}}}if(dis[ed]==dis[0]) return 0;int mn=dis[0];for(int x=ed,j;x!=st;x=e[j^1].v)j=from[x],mn=min(mn,flow[x]);res+=mn*dis[ed];for(int x=ed,j;x!=st;x=e[j^1].v)j=from[x],e[j].c-=mn,e[j^1].c+=mn;return 1; } int main() {scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);st=((n<<1)|1),ed=st+1;for(int i=1;i<=n;i++) scanf("%d",&nd[i]);for(int i=1;i<=n;i++) add(st,i,0,nd[i]);for(int i=1;i<n;i++) add(i,i+1,0,inf);for(int i=1;i+n+a+1<=(n<<1);i++) add(i,i+n+a+1,fa,inf);for(int i=1;i+n+b+1<=(n<<1);i++) add(i,i+n+b+1,fb,inf);for(int i=1;i<=n;i++) add(st,i+n,f,inf);for(int i=1;i<=n;i++) add(i+n,ed,0,nd[i]);while(spfa()); printf("%d\n",res);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lxy8584099/p/10435196.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的bzoj 1221: [HNOI2001] 软件开发的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。