摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

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

系列第三弹

而且曾经写过


网络流24题之第三题——餐巾计划问题

原题见洛谷P1251


题解

我们注意到每天所需要的干净餐巾只能从快洗部、慢洗部或者新购买三条渠道获得,很容易想到使用最小费用最大流来写。

我们将每天所需的干净餐巾和每天产生的脏餐巾作为节点,所有的脏餐巾节点与源点S相连,流量即为餐巾数量,费用为0,所有的干净餐巾与汇点T相连,流量即为餐巾数量,费用为0,两者共同用于控制每天所需餐巾数量不多也不少。

然后将所有的脏餐巾节点与自己下一天的脏餐巾节点连接一条流量无穷,费用为0的边,代表脏餐巾可以留到第二天操作。

再将所有的脏餐巾节点与m天后的干净餐巾节点连接一条流量无穷,费用为f的边,代表脏餐巾经过m天快洗部洗净,每个花费f,充当m天后的干净餐巾;将所有的脏餐巾节点与n天后的干净餐巾节点连接一条流量无穷,费用为s的边,代表脏餐巾经过n天慢洗部洗净,每个花费s,充当n天后的干净餐巾。

最后将所有的干净餐巾与源点S相连,流量无穷,费用为p,代表这一天的干净餐巾可以每个花费p来购买。

最后跑最小费用最大流就完成了。


代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define il inline
#define ll long long
#define inf 0x3F3F3F3F

//快速读入
char gtc();
int rdI();

//链式前向星
struct nd{
    int to,from,cp,cs,nx;
} edge[24005];
int top=2;
int head[4005];
void addEdge(int,int,int,int);

//队列
int h,t;
int q[8005];
void queueReset();
void queuePush(int);
int queuePop();

//网络流
ll mnc;//一定要long long,数据会坑你的
int dis[4005],pre[4005];
bool isi[4005];
bool spfa();
void mcmf();

int N,p,m,f,n,s,S,T;
int r[2005];

int main(){
    N=rdI();
    for(int i=1;i<=N;++i)
        r[i]=rdI();
    p=rdI();m=rdI();f=rdI();n=rdI();s=rdI();
    S=0;
    T=(N<<1)+1;
    //建图===============
    for(int i=1;i<=N;++i){
        addEdge(S,i,r[i],0);
        addEdge(N+i,T,r[i],0);
        addEdge(S,N+i,inf,p);
        if(i<N)
            addEdge(i,i+1,inf,0);
        if(i+m<=N)
            addEdge(i,N+i+m,inf,f);
        if(i+n<=N)
            addEdge(i,N+i+n,inf,s);
    }
    //===================
    mcmf();
    printf("%lld",mnc);
    return 0;
}

il void mcmf(){//最小费用最大流
    while(spfa()){
        int mnf=inf;
        for(int i=pre[T];i;i=pre[edge[i].from])//找最小流量
            mnf=min(mnf,edge[i].cp);
        for(int i=pre[T];i;i=pre[edge[i].from]){//调整流量&计算费用
            edge[i].cp-=mnf;
            edge[i^1].cp+=mnf;
            mnc+=(ll)edge[i].cs*mnf;
        }
    }
}
il bool spfa(){//找增广路
    memset(dis,0x3F,sizeof(dis));
    memset(isi,false,sizeof(isi));
    dis[S]=0;
    queueReset();
    queuePush(S);
    isi[S]=true;
    while(h!=t){
        int u=queuePop();
        isi[u]=false;
        for(int i=head[u];i;i=edge[i].nx){
            int v=edge[i].to;
            if(edge[i].cp&&dis[v]>dis[u]+edge[i].cs){
                pre[v]=i;//记录路线
                dis[v]=dis[u]+edge[i].cs;
                if(!isi[v]){
                    queuePush(v);
                    isi[v]=true;
                }
            }
        }
    }
    return dis[T]!=inf;
}
//队列操作========
il int queuePop(){
    return ++h<8005?q[h]:q[h=0];
}
il void queuePush(int x){
    ++t<8005?(q[t]=x):(q[t=0]=x);
}
il void queueReset(){
    h=t=0;
}
//================
il void addEdge(int x,int y,int cp,int cs){//插边
    edge[top]=(nd){y,x,cp,cs,head[x]};
    head[x]=top;
    //不要忘记反流边
    edge[++top]=(nd){x,y,0,-cs,head[y]};
    head[y]=top++;
}
il char gtc(){//代替getchar()
    static char buff[0xFFFF],*p1=buff,*p2=buff;
    return p1==p2&&(p2=(p1=buff)+fread(buff,1,0xFFFF,stdin),p1==p2)?EOF:*p1++;
}
il int rdI(){//快速读入整数
    int t=0;
    char c=gtc();
    while(c<'0'||c>'9')
        c=gtc();
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=gtc();
    }
    return t;
}

【END】

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code