「Loj 6008」「网络流 24 题」餐巾计划 (最小费用最大流,资源调配)

Loj 2632
题意:见上。

orz 网络流24题之餐巾计划问题 - five20 - 博客园

做法($(c=容量, w=费用)$):
将每天拆点拆成$x_i,y_i$($x$为脏餐巾点,$y$为干净餐巾点)
1、$S$到$x_i$:$(r_i, 0)$,补脏的 (用过的毛巾假设全丢掉,然后再从$S$补偿脏毛巾。以达到一个毛巾用$n$次有流量$n$)
2、$S$到$y_i$:$(∞, P)$,买入毛巾
3、$y_i$到$T$:$(r_i, 0)$,使用毛巾 (用过的毛巾假设全丢掉)
4、$x_i$到$y_{i+M}$:$(∞, F)$,快洗
5、$x_i$到$y_{i+N}$:$(∞, S)$,慢洗
6、$x_i​$到$x_{i+1}​$:$(∞, 0)​$,存着脏毛巾

上述博客思路为:
1、先拆点,然后考虑快洗慢洗、不洗(存着脏毛巾)
2、发现错误(一个毛巾用两次只有流量$1$),修改为舍弃流和补偿流

知识点:
1、资源调配问题,舍弃流和补偿流的方法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {

    const int INF = 2147483647ll;

    struct edge {
        int u, v, cap, w, nxt;
    } ed[500000 + 5];

    int n, m, hd[10000 + 5], en, s, t, ans, V;
    int incf[10000 + 5], dis[10000 + 5], pre[10000 + 5], vis[10000 + 5];

    int ID(int x, int y) {return (x - 1) * m + y;}
    void ins_c(int u, int v, int cap, int w) {
        ed[++en] = (edge){u, v, cap, w, hd[u]}, hd[u] = en;
        ed[++en] = (edge){v, u, 0, -w, hd[v]}, hd[v] = en;
    }

    queue<int > q;
    bool spfa() {
        for (int i = 0; i <= V; ++i) incf[i] = INF, dis[i] = -INF, pre[i] = -1, vis[i] = 0;
        vis[s] = 1, dis[s] = 0, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (e.cap && dis[u] != -INF && dis[e.v] < dis[u] + e.w) {
                    dis[e.v] = dis[u] + e.w;
                    incf[e.v] = min(incf[u], e.cap);
                    pre[e.v] = i;
                    if (!vis[e.v]) vis[e.v] = 1, q.push(e.v);
                }
            }
        }
        return dis[t] != -INF;
    }
    void update() {
        int now = pre[t];
        while (now != -1) {
            ed[now].cap -= incf[t], ed[now ^ 1].cap += incf[t];
            now = pre[ed[now].u];
        }
        ans += incf[t] * dis[t];
    }

    void clean() {
        ans = 0, en = -1, ms(hd, -1);
    }
    int solve() {

        int a, b;

        clean();

        scanf("%d%d%d%d", &a, &b, &n, &m);
        ++n, ++m;

        s = n * m + 1, t = V = n * m + 2;

        for (int i = 1; i <= n; ++i)
        for (int x, j = 1; j < m; ++j) {
            scanf("%d", &x);
            ins_c(ID(i, j), ID(i, j) + 1, 1, x);
            ins_c(ID(i, j), ID(i, j) + 1, INF, 0);
        }
        for (int i = 1; i <= m; ++i)
        for (int x, j = 1; j < n; ++j) {
            scanf("%d", &x);
            ins_c(ID(j, i), ID(j, i) + m, 1, x);
            ins_c(ID(j, i), ID(j, i) + m, INF, 0);
        }
        for (int k, x, y, i = 1; i <= a; ++i) {
            scanf("%d%d%d", &k, &x, &y);
            ++x, ++y;
            ins_c(s, ID(x, y), k, 0);
        }
        for (int k, x, y, i = 1; i <= b; ++i) {
            scanf("%d%d%d", &k, &x, &y);
            ++x, ++y;
            ins_c(ID(x, y), t, k, 0);
        }

        while (spfa()) update();

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------