丰年好大水

果然题越简单数据越鬼…

懵逼的 题目

qwq

扯淡的 题解

题目好长…其实说白了费用就是底下这个玩意

$$
C(x) = \begin{cases}
W_1\,\,x \in [1, T_1]\\
W_2\,\,x \in [T_1 + 1, T_2]\\
W_3\,\,x \in [T_2 + 1, T_3]\\
\cdots \\
W_i\,\,x \in [T_{i - 1} + 1, T_{i}]\\
W_{S_{dq}}\,\,x \in [T_{S_{dq}}, \infty]
\end{cases}
$$

是不是很懵逼? 是不是想到修车 || 美食节去了?

看到底下有一句话$W_{i, j} > W_{i, j - 1}$就很简单了…直接连就好了…

  • $S \to i\,\,\,\,(cost = 0, cap = \infty)$
  • $i \to i’\,\,\,(cost = W_{i, j}, cap = T_{i, j} - T_{i, j - 1})$
  • $i’ \to things_j\,\,\,(cost = 0, cap = \infty), A_{i, j} = true$
  • $things_j \to T\,\,\,(cost = 0, cap = \infty)$

沙茶的 代码

数据真的鬼

/**************************************************************
    Problem: 2245
    User: Cansult
    Language: C++
    Result: Accepted
    Time:12724 ms
    Memory:54544 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7fffffff)
#define bh(x) ((x) + 500)
#define sub(x) ((x) + 1000)
#define rev(a) ((a) ^ 1)
#define int long long
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from, to, next, cost, cap, flow;
    edg() {}
    edg(int fr, int dqt, int ne, int co, int ca): from(fr), to(dqt), next(ne), cost(co), cap(ca), flow(0) {}
}b[MAXM << 1];
int g[MAXN], cntb = -1, dis[MAXN], a[MAXN], pre[MAXN], ans;
int spfa()
{
    bool inq[MAXN];
    memset(inq, false, sizeof(inq));
    memset(dis, 0x7f, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    a[t] = 0, a[s] = 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)
            {
                dis[b[i].to] = dis[dq] + b[i].cost;
                pre[b[i].to] = i;
                a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
                if (!inq[b[i].to])
                    q.push(b[i].to), inq[b[i].to] = true;
            }
    }
    return a[t];
}
void adn(int from, int to, int cap, int cost)
{
    b[++cntb] = edg(from, to, g[from], cost, cap);
    g[from] = cntb;
}
void solve()
{
    while (true)
    {
        int zl = spfa();
        if (!zl)
            break;
        for (int i = t; i != s; i = b[pre[i]].from)
            b[pre[i]].flow += zl, b[rev(pre[i])].flow -= zl, ans += zl * b[pre[i]].cost;
    }
}
main()
{
    memset(g, -1, sizeof(g));
    int n, m;
    scanf("%lld%lld", &m, &n);
    for (int i = 1, src; i <= n; i++)
        scanf("%lld", &src), adn(sub(i), t, src, 0), adn(t, sub(i), 0, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 1, srx; j <= n; j++)
        {
            scanf("%lld", &srx);
            if (srx)
                adn(bh(i), sub(j), INF, 0), adn(sub(j), bh(i), 0, 0);
        }
    for (int i = 1, srn; i <= m; i++)
    {
        adn(s, i, INF, 0);
        adn(i, s, 0, 0);
        scanf("%lld", &srn);
        int srt[50];
        srt[0] = 0, srt[srn + 1] = INF;
        for (int j = 1; j <= srn; j++)
            scanf("%lld", &srt[j]);
        for (int j = 1, srx; j <= srn + 1; j++)
            scanf("%lld", &srx), adn(i, bh(i), srt[j] - srt[j - 1], srx), adn(bh(i), i, 0, -srx);
    }
    solve();
    printf("%lld", ans);
    return 0;
}

/*
2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6
*/

我一定…要…

By Cansult