[LuoguP1251] 餐巾计划问题

摘要

复习一下网络流

一个餐厅在相继的 天里,每天需用一些餐巾。第 天需要 块餐巾 。餐厅可以购买新的餐巾, 每块餐巾的费用为 ;或者把旧餐巾送到快洗部,洗一块需 天,其费用为 分;或者送到慢洗部,洗一块需 ,其费用为

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部, 以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。求最小总花费。

网络流的板子不容易写挂,最烦的就是建模和输入输出的过程,笔者就因为输入输出的问题调了好久~

看题面就知道大概是一个费用流。网络图中的流就是餐巾。对每一天我们拆点,形象地理解为早上和晚上。每天晚上会获得 个脏餐巾且不花钱,而早上我们需要凑齐 个干净的餐巾,这些餐巾可以买来,也可以是之前的脏餐巾洗干净后得来的。于是建模如下:

建边 含义
表示第 天晚上可以不花钱获得 张脏餐巾;
表示第 天早上可以花 买任意数量的干净餐巾;
表示第 天早上把得到的干净餐巾投入使用(交给汇点)。为什么不给当天晚上的结点?因为当天晚上获得的脏餐巾由源点 直接派发。如果不把干净餐巾给汇点就不方便确定满流条件;
表示可以对当天的脏餐巾不做操作,留到第二天晚上;
表示第 天晚上可以花钱快洗,给第 天增加干净餐巾;
表示第 天晚上可以花钱慢洗,给第 天增加干净餐巾;

跑最小费用最大流即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e3+5,M=2e6+5,INF=0x7fffffff;

struct qxx{int nex,t,v,c;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v,int c){e[++cnt]=(qxx){h[f],t,v,c},h[f]=cnt;}
void add_flow(int f,int t,int v,int c){add_path(f,t,v,c),add_path(t,f,0,-c);}
// 最小费用最大流
int s,t,mincost,maxflow;
int dis[N],incf[N],pre[N];
bool vis[N];
queue<int> q;
int spfa(){// 以 c 为键值求最短路
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,incf[s]=INF,incf[t]=0,q.push(s);
    while(q.size()){int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v,&c=e[i].c;
            if(!w||dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c,incf[v]=min(incf[u],w),pre[v]=i;
            if(!vis[v])q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
void update(){// 更新最小费用最大流
    maxflow+=incf[t],mincost+=incf[t]*dis[t];
    for(int u=t;u!=s;u=e[pre[u]^1].t){e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t];
    }
}
int n,r[N],p,m,f,x,y;
signed main(){scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&r[i]);
    scanf("%lld%lld%lld%lld%lld",&p,&m,&f,&x,&y);

    s=0,t=n*2+1;// 源点汇点
    for(int i=1;i<=n;i++){//i 表示早上,i+n 表示晚上
        add_flow(s,i+n,r[i],0);// 晚上会 0 费用获得 r[i] 张脏餐巾
        add_flow(i,t,r[i],0);// 干净的餐巾送往汇点
        add_flow(s,i,INF,p);// 早上可以购买无限个费用为 p 的餐巾
        if(i+1<=n)add_flow(i+n,i+1+n,INF,0);// 可以把当天晚上的脏餐巾留到第二天晚上
        if(i+m<=n)add_flow(i+n,i+m,INF,f);// 快洗
        if(i+x<=n)add_flow(i+n,i+x,INF,y);// 慢洗
    }
    while(spfa())update();
    printf("%lld",mincost);
    return 0;
}

 上一篇
[SCOI2015] 情报传递 [SCOI2015] 情报传递
摘要 有趣的树剖 + 主席树题 奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严
2019.04.09
下一篇 
[POI2014]HOT-Hotels [POI2014]HOT-Hotels
摘要 题意:一颗无根树,每条边长度相同。选 3 个点两两距离相等,有多少种方案? . 不难证明三条路径交汇于一个中心点。以这个中心点为根的话,那么这三个结点深度相同。于是我们枚举根结点,并统计每一个深度的结点数(注意
2019.04.06
  目录