原题链接题意概述在N NN天中每天需要r i r_iri条餐巾餐巾可由花费p pp分购买新的或清洗旧的获得清洗有花费f ff分耗时m mm天的快洗和花费s ss分耗时n nn天的慢洗。求在满足需求下最小花费。建图考虑建图将需求看作边容量花费看作边的费用可转化成最小花费最大流问题。思路 1错误思路 考虑到每天只能看作点但又有需要容量所以考虑拆点将每一天拆解为早上和晚上。连接早上与晚上餐巾使用变脏下图为针对第i天的局部建图cost : plimit : r[i]cost : 0limit : r[i]cost : 0limit : r[i]cost : flimit : r[i]cost : 0limit : r[i m]cost : 0limit : r[im]cost : plimit : r[im]源点i 天早i 天晚上汇点im天早im天晚图仅出示快洗慢洗同理可是这样的建图方式无法保证最优因为此图中仅当汇点接收流量等于需求总量∑ i 1 n r i \sum\limits_{i1}^nr_ii1∑nri时满足需求又因为流量守恒所以源点发出流量汇点接收流量∑ i 1 n r i \sum\limits_{i1}^nr_ii1∑nri即每天餐巾仅通过购买获得所以错误。思路 2正确思路思路1的问题来源于重新利用的餐巾未被计入为新增的流量那么可考虑不连接每天早与晚改为连接源点和每天晚上每天早上和汇点 相当于将脏餐巾看作了新增的流量将干净餐巾直接计入汇点总接收量因为可以延迟洗脏餐巾所以要加上第i天晚上与第i1晚上的一条边。下图为针对第i天的局部建图cost : plimit : r[i]cost : 0limit : r[i]cost : 0limit : r[i]cost : flimit : INFcost : 0limit : r[im]cost : plimit : r[im]cost : 0limit : INFcost : 0limit : r[i1]源点i 天早汇点i 天晚上im天早i1天晚上图仅出示快洗慢洗同理注意: 若清洗后时间超过N NN天则不连边。最后跑费用流即可。#includebits/stdc.husingnamespacestd;#definelllonglong#definepllpairll,ll#definefifirst#definesesecondconstll N1e65,INF0x3f3f3f3f3f3f3f3f;structflow{ll head[N],nxt[N],to[N],limit[N],cnt1,cst[N];voidadd(ll u,ll v,ll w,ll val){nxt[cnt]head[u],head[u]cnt,to[cnt]v,limit[cnt]w,cst[cnt]val;nxt[cnt]head[v],head[v]cnt,to[cnt]u,limit[cnt]0,cst[cnt]-val;}ll cur[N],dis[N],vis[N],T,minc0,maxf0;boolspfa(ll s){memset(vis,0,sizeof(vis));queuellq;memset(dis,INF,sizeof(dis)),dis[s]0,q.push(s);while(!q.empty()){ll nowq.front();q.pop();vis[now]0;for(ll ihead[now];i;inxt[i]){if(limit[i]){ll itto[i],ddis[now]cst[i];if(ddis[it]){dis[it]d;if(!vis[it])vis[it]1,q.push(it);}}}}returndis[T]!INF;}lldfs(ll id,ll res){if(idT)returnres;ll flow0;vis[id]1;for(ll icur[id];ires;inxt[i]){cur[id]i;ll cmin(limit[i],res),itto[i];if(!vis[it]limit[i]dis[id]cst[i]dis[it]){ll kdfs(it,c);limit[i]-k,limit[i^1]k,res-k,flowk,minccst[i]*k;}}if(!flow)dis[id]INF;vis[id]0;returnflow;}lldinic(ll s,ll t){Tt;while(spfa(s)){memcpy(cur,head,sizeof(head));memset(vis,0,sizeof(vis));maxfdfs(s,INF);}returnmaxf;}}g;ll d,m,r[N],p,f,n,s,S,T;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cind;Sd*21,Td*22;for(ll i1;id;i){cinr[i];}cinpmfns;for(ll i1;id;i){g.add(S,i,r[i],p);g.add(i,T,r[i],0);g.add(S,id,r[i],0);if(imd)g.add(id,im,INF,f);if(ind)g.add(id,in,INF,s);if(i!d)g.add(id,id1,INF,0);}g.dinic(S,T);coutg.minc;return0;}
