P1251 napkin planning problem in Luogu (minimum cost and maximum flow)

meaning of the title

A restaurant needs $r_i $napkins on the $I $day. There are three ways to get napkins every day

1. Buy for $p $

2. Send it to the express department for $f $and take it out in $m $days

3. Send it to the slow cleaning department for $s $, and take it out after $n $

Ask the minimum cost when meeting the requirements

Sol

A very good network flow, it should not be difficult to see the cost flow.

First of all, we need to dismantle the site, and then we need to connect every morning and evening

From $S $to $I (0, r_i) $, it means there are $r_i $dirty napkins at night

From $I '$to $T $(0, r_i) $indicates that there are $r_i $new napkins in the morning

From $S $to $i '$with $(p, INF) $, it means that you can provide unlimited napkins at the cost of $p $every morning

From $i $to $i '$with $(0, INF) $, it means that the dirty napkin of every night can be kept to the next night

From $i $to $i '+ M $with $(f, INF) $, indicating fast cleaning

From $i $to $i '+ n $edge $(s, INF) $, indicating slow washing

In this way, we can not only ensure that the daily $R ﹐ I $meets the requirements, but also guarantee the minimum cost. so nice

#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, S, T;
int r[MAXN], p, m, f, n, s;
struct Edge {
    int u, v, w, f, nxt;
}E[MAXN];
int head[MAXN], num;
inline void add_edge(int x, int y, int w, int f) {
    E[num] = (Edge){x, y, w, f, head[x]};
    head[x] = num++;
}
inline void AddEdge(int x, int y, int w, int f) {
    add_edge(x, y, w, f);
    add_edge(y, x, -w, 0);
}
int dis[MAXN], vis[MAXN], Pre[MAXN];
bool SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; dis[S] = 0; q.push(S);
    while(!q.empty()) {
        int p = q.front(); q.pop(); vis[p] = 0;
        for(int i = head[p]; i != -1; i = E[i].nxt) {
            int to = E[i].v;
            if(dis[to] > dis[p] + E[i].w && E[i].f) {
                dis[to] = dis[p] + E[i].w;
                Pre[to] = i;
                if(!vis[to]) vis[to] = 1, q.push(to);
            }
        }
    }
    return dis[T] <= INF;
}
LL F() {
    LL nowflow = INF;
    for(int i = T; i != S; i = E[Pre[i]].u) nowflow = min(nowflow, (LL)E[Pre[i]].f);
    for(int i = T; i != S; i = E[Pre[i]].u) E[Pre[i]].f -= nowflow, E[Pre[i] ^ 1].f += nowflow;
    return nowflow * dis[T];
}
LL MCMF() {
    LL ans = 0;
    while(SPFA()) 
        ans += F();
    return ans;
}
int main() {
    memset(head, -1, sizeof(head));
    N = read(); 
    S = 0; T = 2 * N + 1;
    for(int i = 1; i <= N; i++) r[i] = read();
    p = read(); m = read(); f = read(); n = read(); s = read();
    for(int i = 1; i <= N; i++) AddEdge(S, i, 0, r[i]);
    for(int i = 1; i <= N; i++) AddEdge(S, i + N, p, INF);
    for(int i = 1; i <= N; i++) AddEdge(i + N, T, 0, r[i]);
    for(int i = 1; i <= N; i++) {
        if(i + m <= N) AddEdge(i, i + N + m, f, INF);        
        if(i + n <= N) AddEdge(i, i + N + n, s, INF);
        if(i + 1 <= N) AddEdge(i, i + 1, 0, INF);
    }
    printf("%lld", MCMF());
}

Tags: C++ network

Posted on Fri, 31 Jan 2020 03:09:44 -0800 by synapp2