有些题目不是那么想当然就能做出来的

对算法的理解是最重要的

懵逼的 题目

传送至 Luogu

扯淡的 题解

刚开始我觉得这个题很吼啊, 难度虚高啊 @丁旭高 不就是分成新毛巾和旧毛巾然后新毛巾变成旧毛巾, 旧毛巾洗成新毛巾嘛~于是新毛巾和S连边, 旧毛巾和T和洗完的天数连边…就成了下面这个样子…_(:з」∠)_

这里写图片描述

后来一看不对啊…这个根本不能跑最大流啊…跑最大流的话一定会变成这样: 每一天都买毛巾, 然后全用光, 然后也不洗, 就扔掉(因为这里的流量代表毛巾的使用数量, 所以最大流量就要求毛巾最多, 这肯定是不符合题意的)…GG然后就想…符合题意的话就让新旧毛巾两点之间的边满载就好了…上下界? 不会…GG

然后就翻题解…然后知道了应该这么连边…Emmmmmm…

这里写图片描述

具体连边就是(设新毛巾是X, 旧毛巾是Y):

  1. S -> Xi, 容量为这一天的需求, 费用为买毛巾的钱, 代表这一天最多买需要的新毛巾数量(多买了也没用不是?)
  2. Xi -> T, 容量为需求, 费用为0, 代表…没有代表, 就是用完了…找个地方放(你总得让流量到T不是?_(:з」∠)_)(注意类边上的流量什么都不代表, 这条边上的毛巾我们并不知道他是扔了还是洗了)
  3. S -> Yi, 容量为需求, 费用是0, 代表要洗的毛巾
  4. Xi -> X (i + 1), (放不了LaTeX你们将就QAQ)容量为INF, 费用为0, 代表这一天干净的毛巾留到下一天
  5. Yi -> X (i + 快洗天数), 容量为需求, 费用为快洗费用, 代表这一天不干净的毛巾快洗, 到n久后取到
  6. Yi -> X (i + 慢洗天数)…同上

之所以这么连是因为: 新毛巾不会”变成”旧毛巾…因为旧毛巾的去路一共就两种一个扔了一个洗了, 肯定扔了的最大流量更大, 所以不能在新旧毛巾之间连边…而新图中, 扔或者洗旧毛巾只会对新毛巾的来路产生影响, 而不会影响到最大流量…

然后就是跑费用流…注意龙龙long long

沙茶的 代码

并没有优化, 最慢1612ms真是喜闻乐见

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN (2000 + 5)
#define MAXM (80000 + 5)
#define LL long long
#define rev(a) (((a - 1) ^ 1) + 1)
#define bh(a) ((a < MAXN) ? (a + MAXN) : (a))
#define ubh(a) ((a > MAXN) ? (a) : (a - MAXN))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7ffffff)
const int s = 0, t = (MAXN << 1) - 5;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
    int cost;
    int flow;
    int cap;
    edg() {}
    edg(int a, int b, int c, int d, int e, int f): from(a), to(b), next(c), cost(d), flow(e), cap(f) {}
}b[MAXM];
int g[MAXN << 1];
int cntb;

int n;
int fc, sc, fd, sd;
int nc;
int dn[MAXN];
LL ans;
int pre[MAXN << 1];
int a[MAXN << 1];
void adn(int, int, int, int);
void init();
bool spfa(int);
void solve();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &dn[i]);
    }
    scanf("%d%d%d%d%d", &nc, &fd, &fc, &sd, &sc);
    init();
    solve();
    printf("%lld\n", ans);
    return 0;
}
void adn(int from, int to, int cost, int cap)
{
    b[++cntb] = edg(from, to, g[from], cost, 0, cap);
    g[from] = cntb;
}
void init()
{
    for (int i = 1; i <= n; i++)
    {
        adn(s, i, nc, dn[i]);
        adn(i, s, -nc, 0);

        adn(i, t, 0, dn[i]);
        adn(t, i, 0, 0);

        adn(s, bh(i), 0, dn[i]);
        adn(bh(i), s, 0, 0);

        if (i < n)
        {
            adn(i, i + 1, 0, INF);
            adn(i + 1, i, 0, 0);
        }

        if (i + fd <= n)
        {
            adn(bh(i), i + fd, fc, dn[i]);
            adn(i + fd, bh(i), -fc, 0);
        }

        if (i + sd <= n)
        {
            adn(bh(i), i + sd, sc, dn[i]);
            adn(i + sd, bh(i), -sc, 0);
        }
    }
}
bool spfa(int start)
{
    int dis[MAXN << 1];
    bool inq[MAXN << 1];
    memset(dis, 0x7f, sizeof(dis));
    memset(inq, false, sizeof(inq));
    memset(a, 0, sizeof(a));
    queue<int> q;
    q.push(start);
    inq[start] = true, dis[start] = 0, a[start] = INF;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (b[i].cap > b[i].flow && dis[b[i].to] > dis[dq] + b[i].cost)
            {
                a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
                dis[b[i].to] = dis[dq] + b[i].cost;
                pre[b[i].to] = i;
                if (!inq[b[i].to])
                {
                    q.push(b[i].to);
                    inq[b[i].to] = true;
                }
            }
        }
    }
    return a[t];
}
void solve()
{
    while (spfa(s))
    {
        for (int i = t; i != s; i = b[pre[i]].from)
        {
            b[pre[i]].flow += a[t];
            b[rev(pre[i])].flow -= a[t];
            ans += (LL)b[pre[i]].cost * a[t];
        }
    }
}

By 没写作业还逃课好感度估计已经掉没的 Cansult