Luogu P1251 餐巾计划问题

题目链接 \(Click\) \(Here\)

看到其他人都是用费用流写的，我只能表示：动什么脑子？暴力就完事了！

嗯，这个题应该是一个相当显然的上下界最小费用可行流模型，所以跑就完事了。

\(s -> inn (i)\) \(f = INF\) \(w = buy\) 新买

\(out (i) -> inn (i + fast)\) \(f = INF\) \(w = fastw\) 快洗

\(out(i) ->inn(i + slow)\) \(f = INF\) \(w = sloww\) 慢洗

\(out(i) -> T\) 不洗

\(inn(i)->out(i)\) \(f = [use[i],use[i]]\) \(w=0\) 不洗

还有一个小小的坑了我一下。

\(inn (i) -> inn (i + 1)\) \(f=INF\) \(w=0\) 洗完不用留着

就是这样，然后套路最小费用可行流即可。

#include <bits/stdc++.h>

#define int long long

#define INF 0x3f3f3f3f3f3f3f3f

#define N 4010

#define M 4000010

using namespace std;

struct Graph {

    int cnt, head[N];

    struct edge {

        int nxt, to, f, w;

    }e[M];

    void add_edge (int from, int to, int flw, int val) {

        e[++cnt].nxt = head[from];

        e[cnt].to = to;

        e[cnt].f = flw;

        e[cnt].w = val;

        head[from] = cnt;

    }

    Graph () {

        cnt = -1;

        memset (head, -1, sizeof (head));

    }

}G1;

namespace _EK {

    int vis[N], dis[N], flow[N];

    int pre_edge[N], pre_node[N];

    queue <int> q;

    #define fpop(x) x.front();x.pop()

    bool spfa (int s, int t, Graph &G) {

        memset (vis, 0, sizeof (vis));

        memset (dis, 0x3f, sizeof (dis));

        memset (flow, 0x3f, sizeof (flow));

        vis[s] = true, dis[s] = 0; q.push (s);

        while (!q.empty ()) {

            int u = fpop (q);

            for (int i = G.head[u]; ~i; i = G.e[i].nxt) {

                int v = G.e[i].to;

                if (dis[v] > dis[u] + G.e[i].w && G.e[i].f) {

                    dis[v] = dis[u] + G.e[i].w;

                    flow[v] = min (flow[u], G.e[i].f);

                    pre_edge[v] = i;

                    pre_node[v] = u;

                    if (!vis[v]) {

                        vis[v] = true;

                        q.push (v);

                    }

                }

            }

            vis[u] = false;

        }

        return dis[t] != INF;

    }

}

int EK (int s, int t, Graph &G) {

    int max_flow = 0, min_cost = 0;

    while (_EK :: spfa (s, t, G)) {

        max_flow += _EK :: flow[t];

        min_cost += _EK :: flow[t] * _EK :: dis[t];

        int u = t;

        while (u != s) {

            G.e[_EK :: pre_edge[u] ^ 0].f -= _EK :: flow[t];

            G.e[_EK :: pre_edge[u] ^ 1].f += _EK :: flow[t];

            u = _EK :: pre_node[u];

        }

    }

	return min_cost;

}

void add_len (int u, int v, int f, int w) {

	G1.add_edge (u, v, f, +w);

	G1.add_edge (v, u, 0, -w);

}

int n, bw, qt, st, qw, sw, use[N], flow[N];

int inn (int x) {return n * 0 + x;}

int out (int x) {return n * 1 + x;}

signed main () {

	freopen ("data.in", "r", stdin);

	cin >> n;

	int s = n * 2 + 1, t = n * 2 + 2;

	int ss = n * 2 + 3, tt = n * 2 + 4;

	for (int i = 1; i <= n; ++i) cin >> use[i];

	cin >> bw >> qt >> qw >> st >> sw;

	for (int i = 1; i <= n; ++i) {

		add_len (s, inn (i), INF, bw);

		add_len (out (i), t, INF, 00);

		if (i + qt <= n) add_len (out (i), inn (i + qt), INF, qw);

		if (i + st <= n) add_len (out (i), inn (i + st), INF, sw);

		flow[out (i)] += use[i];

		flow[inn (i)] -= use[i];

	}

	for (int i = 1; i < n; ++i) {

		add_len (inn (i), inn (i + 1), INF, 0);

	}

	for (int i = inn (1); i <= out (n); ++i) {

		if (flow[i] > 0) add_len (ss, i, +flow[i], 0);

		if (flow[i] < 0) add_len (i, tt, -flow[i], 0);

	}

	add_len (t, s, INF, 0);

	cout << EK (ss, tt, G1) << endl;

}