时间戳

首页 > 技术文章 > 网络流24题之餐巾计划问题

网络流24题之餐巾计划问题

hbxblog 2018-09-30 22:34 原文

题目链接：传送门

时间有点赶,所以写的简略一些了.

dalao:这道题不是看看就出来了吗?
me:这道题十分难想啊!!!!图好难建啊!!!!但是想到以后就是一个裸题啊!!

要拆点,将每天拆为早上和晚上(干净的和脏的).
如果不会拆点的话,你可以立即去世了,写网络流的题怎么能不会拆点呢?这是学网络流必备的啊

  • 建立源点汇点.(废话,那个网络流的题不要建)
  • 源点向每天晚上连一条边,流量为当天所需的纸巾数,费用为0。
  • 汇点向每天早上连一条边,流量为当天所需的纸巾数，费用为0。
  • 每天晚上向明天晚上连一条边,流量为inf,费用为0(将当天的脏纸巾留到明天).
  • 连快洗店，慢洗店的边.从当天晚上向过x天(洗纸巾的天数)后那一天早上连一条边,流量为inf,费用为洗纸巾的费用.
  • 连买新纸巾的边，从源点向每天早连一条边,流量为inf，费用为买新纸巾所需费用。

理由呢......自己对着这个看看吧,应该可以明白的.

注意判边界啊

注意开long long 啊

#include<bits/stdc++.h>
#define int long long 
const int inf=1e15;
using namespace std;
typedef long long ll;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
        f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9')
        x=x*10+c-'0',c=getchar();
    return x*f;
}
struct node {
    int to,next,v,w;
} a[1000001];
int dis[10001],f[10001],pre[10001],fa[10001],s,t,n,m,head[10001],cnt,x,y,z,c;
void add(int x,int y,int c,int v) {
    a[++cnt].to=y;
    a[cnt].next=head[x];
    a[cnt].v=c;
    a[cnt].w=v;
    head[x]=cnt;
}
queue < int > q;
int spfa() {
    q.push(s);
    memset(dis,127,sizeof(dis));
    memset(f,0,sizeof(f));
    f[s]=1,dis[s]=0;
    int inf1=dis[s+1];
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        f[now]=0;
        for(int i=head[now]; i; i=a[i].next) {
            int v=a[i].to;
            if(dis[v]>dis[now]+a[i].w&&a[i].v) {
                dis[v]=dis[now]+a[i].w,pre[v]=i,fa[v]=now;
                if(!f[v])
                    f[v]=1,q.push(v);
            }
        }
    }
    if(dis[t]!=inf1)
        return 1;
    return 0;
}
int ans1,ans;
void anser() {
    while(spfa()) {
        int minx=inf;
        for(int i=t; i!=s; i=fa[i])
            minx=min(minx,a[pre[i]].v);
        ans+=minx,ans1+=dis[t]*minx;
        for(int i=t; i!=s; i=fa[i])
            a[pre[i]].v-=minx,(pre[i]%2)?a[pre[i]+1].v+=minx:a[pre[i]-1].v+=minx;
    }
}
int a1[20001];
main() {
    n=read();
    int p,m,f,nn,ss,pp;
    ss=0,t=n*2+1;
    for(int i=1; i<=n; i++)
        a1[i]=read();
    for(int i=1; i<=n; i++)
        add(s,i,a1[i],0),add(i,s,0,0);
    for(int i=1; i<=n; i++)
        add(i+n,t,a1[i],0),add(t,i+n,0,0);
    p=read(),m=read(),f=read(),nn=read(),ss=read();
    for(int i=1; i<=n; i++)
        if(i+n+1<t)
            add(i+n,i+n+1,inf,0),add(i+n+1,i+n,0,0); 
    for(int i=1; i<=n; i++)
        if(i+m+n<t)
            add(i,i+n+m,inf,f),add(i+n+m,i,0,-f);
    for(int i=1; i<=n; i++)
        if(i+nn+n<t)
            add(i,i+nn+n,inf,ss),add(i+nn+n,i,0,-ss);
    for(int i=1; i<=n; i++)
        add(s,i+n,1000000,p),add(i+n,s,0,-p);
    anser();
    printf("%lld",ans1);
}

推荐阅读