2023年7月30日发(作者：)

餐⼱计划问题题解：⽹络流⼆⼗三题中⽐较有意思的⼀道题。正常能想到的建图⽅法是：1.拆点，将每⼀天拆成早上和晚上；2.早上向晚上连边，容量为当天所需餐⼱数；3.今天晚上向明天晚上连边，容量为正⽆穷；4.S向早上连边，容量正⽆穷，费⽤为买餐⼱费⽤；5.每天晚上向慢洗后的那⼀天早上连边，容量正⽆穷，费⽤为慢洗费⽤；6.每天晚上向快洗后的那⼀天早上连边，容量正⽆穷，费⽤为快洗费⽤；7.每天晚上向T连边，容量正⽆穷。然后，突然发现不知道怎么求。由于流量守恒定理：流不会凭空产⽣，也不会凭空消失，它只会从源点流向汇点。我们发现，⽤过的餐⼱会直接被扔。图建错了……这时我们需要打破僵局，直接⼲掉早上向晚上的连边，改为：1.源点向晚上连边，容量为当天餐⼱数，费⽤为0，代表此时应有这些餐⼱等待处理；2.早上向汇点连边，容量为当天餐⼱数，费⽤为0，代表此时应有这些餐⼱等待死亡；然后最⼩费⽤流。得到最⼩费⽤即为答案。代码：#include#include#include#includeusing namespace std;#define N 4050#define ll long longconst int inf = 0x3f3f3f3f;const ll Inf = 0x3f3f3f3f3f3f3f3fll;inline int rd(){ int f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c;}int n,m,S,T,a,b,c,d,hed[N],cnt=-1;struct EG{ int to,nxt; ll w,c;}e[6*N];void ae(int f,int t,ll w,ll c){ e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; e[cnt].c = c; hed[f] = cnt;}ll dep[N],fl[N];int pre[N],fa[N];bool vis[N];queueq;bool spfa(){ memset(dep,0x3f,sizeof(dep)); dep[S]=0,fl[S]=Inf,vis[S]=0;(S); while(!()) { int u = (); (); for(int j=hed[u];~j;j=e[j].nxt) { int to = e[j].to; if(e[j].w&&dep[to]>dep[u]+e[j].c) { dep[to] = dep[u]+e[j].c; fl[to] = min(fl[u],e[j].w); pre[to] = j,fa[to] = u; if(!vis[to]) { vis[to] = 1; (to); } } } vis[u] = 0; } return dep[T]!=Inf;}ll mcmf(){ ll ret = 0; while(spfa()) { ret+=fl[T]*dep[T]; int u = T; while(u!=S) { e[pre[u]].w-=fl[T]; e[pre[u]^1].w+=fl[T]; u = fa[u]; } } return ret;}int main(){ n = rd(); S=0,T=1; memset(hed,-1,sizeof(hed)); for(int x,i=1;i<=n;i++) { x = rd(); ae(S,i<<1|1,x,0); ae(i<<1|1,S,0,0); ae(i<<1,T,x,0); ae(T,i<<1,0,0); } m = rd(),a = rd(),b = rd(),c = rd(),d = rd(); for(int i=1;i<=n;i++) { ae(S,i<<1,Inf,m); ae(i<<1,S,0,-m); } for(int i=1;i

Processing math: 100%