简要题意
一家公司销售一种商品，在时刻 (i) 可以需要 (U_i) 份商品。第 (i) 时刻向生产方购买 (1) 份商品需要 (d_i) 的代价。(i-1) 时刻的 (1) 份商品滞留到 (i) 时刻，需要花费 (m) 的代价，且一共只能滞留 (S) 份商品。
问经营 (n) 个时刻的最小花费。
(0\leq n\leq 50, 0\leq m \leq 10, 0\leq S\leq 10000,0 \leq U_i \leq 10000,0 \leq d_i \leq 100)
对于 (i) 时刻，建立点 (i)，然后考虑连边：
- 对于滞留商品，我们连边((i-1,i,S,m))（这一点显然易见）。
- 对于需要商品，我们像餐厅计划问题一样，建立超级汇点(T)，然后连边((i,T,U_i,0))。
- 对于购买商品，我们像餐厅计划问题一样，建立超级源点(S)，然后连边((S,i,+\infty,d_i))。
这里再解释一下连边：需要商品时，不能从上一个节点连边，因为剩余不方便计算。但是我们如果连向汇点，那么就直接限制了流量，也就是说，如果要有流量，那么必须要有 (U_i) 的流量。购买商品时，没有商品份数限制，因此流量为 (+\infty)，买一份需要 (d_i)，所以费用时 (d_i)。总之，这里流量时商品个数，费用时花费。
然后直接跑 (S) 为源 (T) 为汇的最小费用最大流即可。时间复杂度 (O(\operatorname{mcmf}(n,n)))。
#include
#define int long long
using namespace std;
int n,m,s;
namespace MCMF{
struct edge{
int nxt,to,cap,cost;
} g[100005];
int head[100005],ec=-1;
void add(int from,int to,int cap,int cost){
g[++ec].nxt=head[from];
g[ec].to=to;
g[ec].cap=cap;
g[ec].cost=cost;
head[from]=ec;
}
void add_edge(int from,int to,int cap,int cost){
add(from,to,cap,cost);
add(to,from,0,-cost);
}
queue q;
bool vis[100005];
int flow[100005];
int dis[100005];
int pre[100005];
int last[100005];
bool spfa(int s,int t){
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s);
vis[s]=1;
dis[s]=0;
pre[t]=-1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(g[i].cap>0 && dis[v]>dis[u]+g[i].cost){
dis[v]=dis[u]+g[i].cost;
pre[v]=u;
last[v]=i;
flow[v]=min(flow[u],g[i].cap);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return pre[t]!=-1;
}
pair MCMF(int s,int t){
int maxflow=0,mincost=0;
while(spfa(s,t)){
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
while(now!=s){
g[last[now]].cap-=flow[t];
g[last[now]^1].cap+=flow[t];
now=pre[now];
}
}
return make_pair(maxflow,mincost);
}
}
int S,T;
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
memset(MCMF::head,-1,sizeof(MCMF::head));
MCMF::ec=-1;
cin>>n>>m>>s;
S=0,T=n+1;
for(int i=1,u;i>u;
MCMF::add_edge(i,T,u,0);
}
for(int i=1,d;i>d;
MCMF::add_edge(S,i,LLONG_MAX,d);
}
for(int i=2;i
Original: https://www.cnblogs.com/zheyuanxie/p/p2517.html
Author: xiezheyuan
Title: P2517 [HAOI2010]订货
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604581/
转载文章受原作者版权保护。转载请注明原作者出处！