[题解] PowerOJ 1745 餐巾计划问题 (最小费用最大流)

- 传送门 -

　https://www.oj.swust.edu.cn/problem/show/1745

# 1745: 餐巾计划问题

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 324 Accepted: 112 Page View: 760

Description

一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1， 2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s< f 分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。编程任务：编程找出一个最佳餐巾使用计划.

Input

由文件input.txt提供输入数据。文件第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n是慢洗部洗一块餐巾需用天数；s是慢洗部洗一块餐巾需要的费用。接下来的N 行是餐厅在相继的N 天里，每天需用的餐巾数。

Output

程序运行结束时，将餐厅在相继的N 天里使用餐巾的最小总花费输出到文件output.txt 中。

3 10 2 3 3 2
5
6
7

145

Source

线性规划与网络流24题

- 思路 -

　建模建模!!!
　设每天用完的餐巾为 X 集合, 由每天的需求数和前一天留下来的组成.
　所以从 S 向每个 Xi 连一条容量为 ri ，费用为 0 的有向边. (ri 表示每天的需求).
　从每个 Xi 向 Xi+1 (i+1<=N) 连一条容量为 inf，费用为 0 的有向边.
　
　每天供给的干净餐巾为 Y 集合, 由每天新买的和之前洗完的组成.
　所以从 S 向每个 Yi 连一条容量为 inf，费用为 p 的有向边.
　从每个 Xi 向 Yi+m (i+m<=N) 连一条容量为 inf，费用为 f 的有向边.
　从每个 Xi 向 Yi+n (i+n<=N) 连一条容量为 inf，费用为 s 的有向边.
　
　从每个Yi向T连一条容量为ri，费用为0的有向边。
　当最后这几条边满流时, 所得到的费用就是答案.
　
　细节见代码.
　

- 代码 -

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
const int N = 2e3;
const int M = 1e6;
const int inf = 0x3f3f3f3f;
queue<int> q;
 
int NXT[M], FRM[M], TO[M];
int HD[N], DIS[N], VIS[N], V[M];
int CST[M], PRE[N];
int days, p, m, f, n, s, ans, flow;
int sz, cnt, tot, ss, tt;
 
void add(int x, int y, int z, int c) {
    FRM[sz] = x; TO[sz] = y; V[sz] = z;
    NXT[sz] = HD[x]; HD[x] = sz; CST[sz++] = c;
    FRM[sz] = y; TO[sz] = x; V[sz] = 0;
    NXT[sz] = HD[y]; HD[y] = sz; CST[sz++] = -c;
}
 
bool spfa() {
    for (int i = 0; i <= tt; ++i)
        PRE[i] = 0, DIS[i] = inf;
    DIS[ss] = 0;
    q.push(ss);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        VIS[u] = 0;
        for (int i = HD[u]; i != -1; i = NXT[i]) {
            int v = TO[i];
            if (V[i] > 0 && DIS[v] > DIS[u] + CST[i]) {
                DIS[v] = DIS[u] + CST[i];
                PRE[v] = i;
                if (!VIS[v]) {
                    VIS[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return (DIS[tt] != inf);
}
 
int mcmf() {
    int  fr = 0, cost = 0, tmp;
    while (spfa()) {
        fr ++;
        tmp = inf;
        for (int i = tt; i != ss; i = FRM[PRE[i]]) {
            if (tmp > V[PRE[i]]) tmp = V[PRE[i]];
        }
        for (int i = tt; i != ss; i = FRM[PRE[i]]) {
            V[PRE[i]] -= tmp;
            V[PRE[i]^1] += tmp;
        }
        cost += tmp * DIS[tt];
        tmp = inf;
    }
    return cost;
}
 
int main() {
    memset(HD, -1, sizeof (HD));
    scanf("%d%d%d%d%d%d", &days, &p, &m, &f, &n, &s);
    ss = 0, tt = days * 2 + 1;
    for (int i = 1, x; i <= days; ++i) {
        scanf("%d", &x);
        add(ss, i, x, 0);
        add(i + days, tt, x, 0);
        add(ss, i + days, inf, p);
        if (i < days) add(i, i + 1, inf, 0);
        if (i + m <= days) add(i, i + days + m, inf, f);
        if (i + n <= days) add(i, i + days + n, inf, s);
    }
    printf("%d
", mcmf());
    return 0;
}