Description

你的公司接到了一批订单. 订单要求你的公司提供 \(n\) 类产品, 产品被编号为 \(1 \sim n\), 其中第 \(i\) 类产品共需要 \(C_i\) 件. 公司共有 \(m\) 名员工, 员工被编号为 \(1 \sim m\) 员工能够制造的产品种类有所区别. 一件产品必须完整地由一名员工制造, 不可以由某名 员工制造一部分配件后, 再转交给另外一名员工继续进行制造.

我们用一个由 \(0\) 和 \(1\) 组成的 \(m \times n\) 的矩阵 \(A\) 来描述每名员工能够制造哪些产品. 矩阵的行和列分别被编号为 \(1 \sim m\) 和 \(1 \sim n\),\(A_{i,j}\) 为 \(1\) 表示员工 \(i\) 能够制造产品 \(j\), 为 \(0\) 表示员工 \(i\) 不能制造产品 \(j\).

如果公司分配了过多工作给一名员工, 这名员工会变得不高兴. 我们用愤怒值来描述某名员工的心情状态. 愤怒值越高, 表示这名员工心情越不爽, 愤怒值越低, 表示这名员工心情 越愉快.

员工的愤怒值与他被安排制造的产品数量存在某函数关系, 鉴于员工们的承受能力不同, 不同员工之间的函数关系也是有所区别的. 对于员工 \(i\), 他的愤怒值与产品数量之间的函数是一个 \(S_{i}+1\) 段的分段函数. 当他制造第 \(1 \sim Ti,1\) 件产品时, 每件产品会使他的愤怒值增加 \(W_{i,1}\), 当他制造第 \(T_{i,1}+1 \sim T_{i,2}\) 件产品时, 每件产品会使他的愤怒值增加 \(W_{i,2} \ldots\)

为描述方便, 设 \(T_{i,0} = 0, T_i, S_{i+1} = \infty\), 那么当他制造第 \(T_{i,j-1}+1 \sim Ti,j\) 件产品时, 每件产品会使他的愤怒值增加 \(Wi,j (1 \leq j \leq S_{i}+1)\). 你的任务是制定出一个产品的分配方案, 使得订单条件被满足, 并且所有员工的愤怒值之和 最小. 由于我们并不想使用 Special Judge, 也为了使选手有更多的时间研究其他两道题目, 你只需要输出最小的愤怒值之和就可以了.

Input

第一行包含两个正整数 \(m\) 和 \(n\), 分别表示员工数量和产品的种类数; 第二行包含 \(n\) 个正整数, 第 \(i\) 个正整数为 \(C_i\);

以下 \(m\) 行每行 \(n\) 个整数描述矩阵 \(A\);

下面 \(m\) 个部分, 第 \(i\) 部分描述员工 \(i\) 的愤怒值与产品数量的函数关系. 每一部分 由三行组成: 第一行为一个非负整数 \(S_i\), 第二行包含 \(S_i\) 个正整数, 其中第 \(j\) 个正整数为 \(T_{i,j}\), 如果 \(S_i = 0\) 那么输入将不会留空行 (即这一部分只由两行组成). 第三行包含 \(S_{i+1}\) 个正整数, 其中第 \(j\) 个正整数为 \(W_{i,j}\).

Output

仅输出一个整数, 表示最小的愤怒值之和.

Sample Input

2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6

Sample Output

24

Data Range

对于所有数据,\(1 \leq m, n \leq 250, 0 \leq S_i \leq 5, 0 \leq A_{i,j} \leq 1, 0 \lt T_{i,j} \lt T_{i,j+1}, 0 \lt W_{i,j} \lt W_{i,j+1}\), 所有数据不大于 \(10^8\)

Explanation

一眼瞪出来的费用流, 由于 SPFA 的贪心性质, 我们可以假定每一次增广的时候总会选取 最佳的那一段路程或线段, 所以我们把分段函数分段, 就建完费用流了

把 1 写成 i 调了好久~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 2010, maxm = 500100, maxN = 260, maxS = 11;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const int infinit_i = 0x7fffffff;

class MaxFlowMinCost
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    lli dist[maxn];
    edge *edges[maxn], epool[maxm], *from[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool inque[maxn];
    bool spfa(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            inque[i] = false, dist[i] = infinit, from[i] = NULL;
        que.push(s);
        inque[s] = true, dist[s] = 0;
        while (!que.empty()) {
            int p =que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    lli max_flow, min_cost;
    void eval(void)
    {
        max_flow = 0;
        min_cost = 0;
        while (spfa()) {
            lli tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= tmp,
                ep->rev->flow += tmp;
            max_flow += tmp;
            min_cost += tmp * dist[t];
        }
        return ;
    }
} graph;

int n, m;
int C[maxN], A[maxN][maxN],
    S[maxN], T[maxN][maxS], W[maxN][maxS];

int main(int argc, char** argv)
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &C[i]);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &A[i][j]);
    // Reading functions
    for (int i = 1; i <= m; i++) {
        scanf("%d", &S[i]);
        for (int j = 1; j <= S[i]; j++)
            scanf("%d", &T[i][j]);
        T[i][S[i] + 1] = infinit_i;
        for (int j = 1; j <= S[i] + 1; j++)
            scanf("%d", &W[i][j]);
    }
    // Building graph according to MCMF
    graph.n = n + m + 2;
    graph.s = n + m + 1;
    graph.t = n + m + 2;
    for (int i = 1; i <= n; i++)
        graph.add_edge(graph.s, i, C[i], 0);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (A[i][j])
                graph.add_edge(j, n + i, infinit, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= S[i] + 1; j++)
            graph.add_edge(n + i, graph.t, T[i][j] - T[i][j - 1], W[i][j]);
    // Evaluating
    graph.eval();
    lli res = graph.min_cost;
    printf("%lld\n", res);
    return 0;
}