餐巾计划问题(最小费用最大流)

发表于 | 分类于

​ 一道最小费用最大流的模板题，对于最小费用最大流，比较简单的做法是不断地在残量网络上跑SPFA，每次找到从源点到汇点花费最小的路径，并且跑完这条路径上的流量，直到从源点无法到达汇点为止。

​ 这道题的建图比较有意思。我们设第i天需要nd[i]块餐巾，购买一块餐巾的费用是newp，慢洗需要sloc天，花费是slop；快洗需要fstc天，花费是fstp。首先将n天拆点，设xi为第i天开始时拥有的餐巾数量，yi为第i天结束后用过的餐巾数量。则我们从源点向每个xi连一条费用为0，流量为nd[i]的边来限制，同时从每个yi都向汇点连一条流量为nd[i]，费用为0的边进行限制。

​ 接下来对于每条规则进行限制：

  1. 来源为新购买的餐巾：从源点向每个yi连一条流量为无穷，花费为newp的边；
  2. 用过的餐巾送到慢洗部：从xi向y(i+sloc)连一条流量为无穷，花费为slop的边；
  3. 用过的餐巾送到快洗部：从xi向y(i+fstc)连一条流量为无穷，花费为fstp的边；
  4. 用过的餐巾留到下一天再处理：从xi向x(i+1)连一条流量为无穷，花费为0的边。

​ 这样建图之后，能够保证最大流为,最小花费即为最大流的最小费用。

对于反边，要注意流量为0，花费为相反数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
long long had[500005],nxt[400009],point[400009],val[4000009];
long long dis[500005];
long long flow[4000009];
long long tot=1;
inline void add(long long x,long long y,long long v,long long f)
{
    tot++;
    nxt[tot]=had[x];
    point[tot]=y;
    had[x]=tot;
    val[tot]=v;
    flow[tot]=f;
    tot++;
    nxt[tot]=had[y];
    point[tot]=x;
    had[y]=tot;
    val[tot]=-v;
    flow[tot]=0;
}
long long s,T;
bool vis[500005];
long long up[500005];
long long fw[500005];
inline bool spfa()
{
    queue<long long> q;
    memset(dis,0x3f,sizeof(dis));
    long long big=dis[0];
    dis[s]=0;
    q.push(s);
    memset(up,0,sizeof(up));
    while(!q.empty())
    {
        long long t=q.front();
        q.pop();
        vis[t]=0;
        for(long long i=had[t];i;i=nxt[i])
        {
            long long to=point[i];
            if(flow[i]==0)continue;
            if(dis[to]>dis[t]+val[i])
            {
                dis[to]=dis[t]+val[i];
                up[to]=t;
                fw[to]=i;
                if(vis[to]==0)
                {
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
    }
    if(dis[T]==big)return 0;
    return 1;
}
long long fl()
{
    long long cost=0;
    while(spfa())
    {
        long long mf=1e9;
        for(long long i=T;i!=s;i=up[i])
            mf=min(mf,flow[fw[i]]);
        for(long long i=T;i!=s;i=up[i])
        {
            flow[fw[i]]-=mf;
            flow[fw[i]^1]+=mf;
        }
        cost+=dis[T]*mf;
    }
    return cost;
}
long long n;
long long nd[20004];
long long newp,fstp,slop;
long long fstc,sloc;
long long big=1e9;
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
        scanf("%d",&nd[i]);
    scanf("%lld%lld%lld%lld%lld",&newp,&fstc,&fstp,&sloc,&slop);
    s=0;
    T=2*n+10;
    for(long long i=1;i<=n;i++)
    {
        add(s,i,0,nd[i]);
        add(i+n,T,0,nd[i]);
        add(s,i+n,newp,big);
        if(i+sloc<=n)
        add(i,(i+sloc)+n,slop,big);
        if(i+fstc<=n)
        add(i,(i+fstc)+n,fstp,big);
        if(i+1<=n)
        add(i,i+1,0,big);
    }
    printf("%lld",fl());
    return 0;
}