题解 P1251 【网络流24题】餐巾计划问题

天泽龟 · 2019-03-17 23:35:55 · 题解

从上到下翻完所有题解，虽然大多数都清楚地说明了如何去建图，但没有一篇去解释为什么要这样建图。况且建图时候很多奇奇怪怪的小细节并不符合常规的思路，如果没有真正去弄懂它，即使这道题水过，考场上也不会想清楚的。

本篇题解将充分，全面地来解释建图的过程，以及其中的诸多细节。也欢迎各位指出其中不足。

拿到题后~~根据标签~~大体上可以判断出这是一个最小费用流。题目中有一段这样说道：

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

于是整理得，我们需要支持以下操作：

将脏餐巾以f元/条送到快洗部，过m天后，干净餐巾送回来使用
将脏餐巾以s元/条送到慢洗部，过n天后，干净餐巾送回来使用
延期送洗（可能会出现之后餐巾需求过少，并不需要所有餐巾的情况）
以p元/条购买新的餐巾

于是本题第一个难点就来了：如何处理脏餐巾和干净餐巾？

我们可以想到，每天开始的时候只有干净的餐巾可使用，每天结束的时候仅有脏的餐巾需要操作。于是将每天拆成两个点：起始点与结束点，分别处理不同时间段所需操作。

于是也可以想到：

送到快洗部属于结束点操作，连向i+m天后的起始点，费用为f（表示餐巾洗好了，可使用）
送到慢洗部属于结束点操作，连向i+n天后的起始点，费用为s
延期送洗属于结束点操作，连向i+1的结束点，不需费用。
购买新的餐巾的操作也应是连向每天起始点的边，目前并没有确定从哪连的，但费用为p。

以上操作流量均为inf.

好了，到这里你有没有发现以上操作有什么共同点？

没错，他们都是连向起始点的有向边！

\color{red} update: \text{延期送洗的操作应连向的是结束点，}

\color{red} \text{感谢}$ $Specialzyy$ $\color{red} \text{指出错误。}

\color{red} update: \text{话虽如此，但此题没有从起始点向外连的边，仍满足线性。}

事实上，网络流24题的全称为“网络流与线性规划24题”，这也就告诉我们： 网络流的建图一定有顺序的，建的边一定是沿源点流向汇点，否则图就会不流通。

所以现在我们就弄明白了：我们应该将源点连接每天的结束点，而不是他们的起始点；起始点连向他们的汇点，容量为这天所需的餐巾数量，费用为0。

此外购买餐巾直接从源点购买即可。

之后跑一个裸的费用流即可。上我丑陋的代码：

#include <iostream>
#include <cstring>
#include <queue>
#define N 2*n+1
#define inf 2147483647
using namespace std;

struct ed{
    int u,next,w,f;
}e[300000];
long long n,p,b,f,a,s,st=1,cost,ans;
int r[100000],d[100000],fir[100000],c[100000];
queue<int> q; bool v[100000];

bool spfa()
{
    for (int i=0;i<=N;i++) d[i]=inf/2,v[i]=0,c[i]=fir[i];
    q.push(0); v[0]=1; d[0]=0;
    while (!q.empty())
    {
        int k=q.front(); q.pop(); v[k]=0;
        for (int i=fir[k];i;i=e[i].next)
        {
            int u=e[i].u,w=e[i].f;
            if (d[u]>d[k]+w&&e[i].w)
            {
                d[u]=d[k]+w; if (!v[u]) v[u]=1,q.push(u); 
            } 
        }
    }
    return (d[N]<inf/2);
}

int dfs(int p,int now)
{
    if (p==N) {
        v[N]=1; ans+=now; return now;
    }
    int mw=0,used=0;  v[p]=1;
    for (int i=c[p];i;i=e[i].next){
        c[p]=1; int u=e[i].u,w=e[i].f;
        if ((!v[u]||u==N)&&d[u]==d[p]+w&&e[i].w)
        if (mw=dfs(u,min(now-used,e[i].w)))
        {
            e[i].w-=mw; e[i^1].w+=mw; used+=mw;
            cost+=w*mw; if (used==now) break;
        }
    }
    return used;
}

long long dinic()
{
    while (spfa())
    {
        v[N]=1;
        while (v[N])
        {
            memset(v,0,sizeof(v));
            dfs(0,inf);
        }

    }
    return cost;
}

void add(int x,int y,int w,int f)
{
    e[++st].u=y; e[st].next=fir[x]; e[fir[x]=st].w=w; e[st].f=f;
    e[++st].u=x; e[st].next=fir[y]; e[fir[y]=st].w=0; e[st].f=-f;

}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>r[i];
        add(0,i,r[i],0); add(i+n,N,r[i],0);
        //源点连接结束点，起始点连向他们的汇点。
    }
    cin>>p>>a>>f>>b>>s;
    for (int i=1;i<=n;i++)
    {
        add(0,i+n,inf,p);  //从源点购买餐巾
        if (i+1<=n) add(i,i+1,inf,0);   //把今天的脏毛巾拖到明天 
        if (i+a<=n) add(i,i+n+a,inf,f); //把餐巾送到快洗部
        if (i+b<=n) add(i,i+n+b,inf,s); //把餐巾送到慢洗部
    }
    //可以注意到，以上的连边均是由源点向汇点的。
    cout<<dinic()<<endl;
}