【题目大意】n种菜，每种有pi份，有m位厨师，第i位厨师做第j道菜的时间是cij，求将所有菜做完花费的最小时间

【题目分析】

【相对暴力】

直接进行拆点，类似修车
（其实就是一样的
但是问题在于如果直接拆的话点数过多，就会TLE
于是就需要想办法进行优化

（建议不熟的话先把暴力写会）

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define ll int
using namespace std;
const int MAXM = 113234;
const int INF = 2e9 + 7;
typedef pair<int, int> P;
struct note
{
    int to;
    int nt;
    int rev;
    ll cost;
    ll cal;
};
int tn, tm, tk, sum;
int p[MAXM], a[200][200];
void read()
{
    scanf("%d%d", &tn, &tm);
    for (int i = 1; i <= tn; i++)
        scanf("%d", &p[i]), sum += p[i];
    for (int i = 1; i <= tn; i++)
        for (int j = 1; j <= tm; j++)
            scanf("%d", &a[i][j]);
}
struct edge
{
    note arr[7000000];
    int  st[MAXM];
    ll   dis[MAXM];
    ll   h[MAXM];
    int  cur[MAXM];
    int  depth[MAXM];
    int  pre[MAXM];
    int  pree[MAXM];
    int  top;
    int n, m, s, t, siz, k;
    edge()
    {
        memset(st, -1, sizeof(st));
        memset(depth, -1, sizeof(depth));
        memset(dis, -1, sizeof(dis));
        top = 0;
    }
    void init()
    {
        memset(st, -1, sizeof(st));
        memset(depth, -1, sizeof(depth));
        memset(dis, -1, sizeof(dis));
        top = 0;

    }
    void build(int ts, int tt)
    {
        s = ts, t = tt, siz = tt;
        n = tn; m = tm;
        for (int i = 1; i <= n; i++)
            add(s, i, p[i], 0);
        for (int i = 1; i <= n; i++)
        {
                for (int j1 = 1; j1 <= m; j1++)
                    for (int k = 1; k <= sum; k++)
                    {
                        add(i, n + (j1 - 1) * sum + k, 1, a[i][j1] * k);
                       
                    }
        }
        for (int i = n + 1; i < t; i++)
            add(i, t, 1, 0);
    }
    bool dep()
    {
        queue<int> q;
        q.push(s);
        memset(depth, -1, sizeof(depth));
        depth[s] = 0;
        while (!q.empty())
        {
            int v = q.front(); q.pop();
            for (int i = st[v]; i != -1; i = arr[i].nt)
            {
                int to = arr[i].to;
                if (!arr[i].cal)
                    continue;
                if (depth[to] != -1)
                    continue;
                depth[to] = depth[v] + 1;
                q.push(to);
            }
        }
        return (depth[t] != -1);
    }
    void add(int x, int y, ll z, ll c)
    {
        top++; arr[top] = { y,st[x],top + 1,c,z }; st[x] = top;
        top++; arr[top] = { x,st[y],top - 1,-c,0 }; st[y] = top;
    }
    ll dfs(int now, ll val)
    {
        if (now == t || !val)
            return val;
        ll flow = 0;
        for (int& i = cur[now]; i != -1; i = arr[i].nt)
        {
            int to = arr[i].to;
            if (depth[to] != depth[now] + 1)
                continue;
            ll f = dfs(to, min(arr[i].cal, val));
            if (!f || !arr[i].cal)
                continue;
            flow += f;
            arr[i].cal -= f;
            arr[arr[i].rev].cal += f;
            val -= f;
            if (!val)
                return flow;
        }
        return flow;
    }
    ll dinic()
    {
        ll flow = 0;
        ll f;
        while (dep())
        {
            for (int i = 0; i <= siz; i++)
                //这里
                cur[i] = st[i];
            while (f = dfs(s, INF))
                flow += f;
        }
        return flow;
    }
    ll min_cost(ll f)
    {
        ll res = 0;
        while (f > 0)
        {
            fill(dis, dis + 1 + siz, INF);
            priority_queue<P, vector<P>, greater<P>> q;
            dis[s] = 0;
            q.push(P(0, s));
            while (!q.empty())
            {
                P p = q.top(); q.pop();
                int v = p.second;
                if (dis[v] < p.first) continue;
                for (int i = st[v]; i != -1; i = arr[i].nt)
                {
                    note& e = arr[i];
                    if (e.cal > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to])
                    {
                        dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                        pre[e.to] = v;
                        pree[e.to] = i;
                        q.push(P(dis[e.to], e.to));
                    }
                }
            }
            if (dis[t] == INF)    return -1;
            for (int i = 0; i <= siz; i++)
                //这里改了
                h[i] += dis[i];
            ll d = f;
            //printf("2\n");
            for (int i = t; i != s; i = pre[i])
            {
                d = min(d, arr[pree[i]].cal);
            }
            f -= d;
            res += d * h[t];
            for (int i = t; i != s; i = pre[i])
            {
                arr[pree[i]].cal -= d;;
                int rev = arr[pree[i]].rev;
                arr[rev].cal += d;
            }
            //printf("3\n");
        }
        return res;
    }
};
edge road, new_road;
edge tmp;
int main()
{
    read();
    road.init();
    road.build(0, tn + sum * tm + 1);
    printf("%d", road.min_cost(sum));
    return 0;
}

【动态加边】

先思考每次遍历的时候会用到哪些边
找一次增广路最多只能找到一条流量为1的增广路
（因为最后连接终点的边流量均为1）
所以说最开始直接把所有的点和边都建好会消耗大量时间

所以我们最初只建完成倒数第一件食物的那一层边

将寻找增广路的过程拆开来看，观察每次查找到增广路之后
被更新的那条边就已经被使用过了，然后将相对应的边加进去

也不是那条边，而是那条边对应的那名厨师，在他的后面加边
说明这名厨师已经在做一道菜了，如果想让他做另外一道菜
就需要排在下一位了

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define ll int
using namespace std;
const int MAXM = 113234;
const int INF = 2e9 + 7;
typedef pair<int, int> P;
struct note
{
    int to;
    int nt;
    int rev;
    ll cost;
    ll cal;
};
int tn, tm, tk, sum;
int p[MAXM], a[200][200];
int ha[MAXM], co[MAXM];
void read()
{
    scanf("%d%d", &tn, &tm);
    for (int i = 1; i <= tn; i++)
        scanf("%d", &p[i]), sum += p[i];
    for (int i = 1; i <= tn; i++)
        for (int j = 1; j <= tm; j++)
            scanf("%d", &a[i][j]);
}
struct edge
{
    note arr[7000000];
    int  st[MAXM];
    ll   dis[MAXM];
    ll   h[MAXM];
    int  cur[MAXM];
    int  depth[MAXM];
    int  pre[MAXM];
    int  pree[MAXM];
    int  top;
    int n, m, s, t, siz, k;
    edge()
    {
        memset(st, -1, sizeof(st));
        memset(depth, -1, sizeof(depth));
        memset(dis, -1, sizeof(dis));
        top = 0;
    }
    void init()
    {
        memset(st, -1, sizeof(st));
        memset(depth, -1, sizeof(depth));
        memset(dis, -1, sizeof(dis));
        top = 0;

    }
    void build(int ts, int tt)
    {
       
        n = tn; m = tm; s = ts, t = sum*m+n+1, siz = sum*m+n+1;
        for (int i = 1; i <= n; i++)
            add(s, i+sum*m, p[i], 0);
        s = 0, t = sum * m + n + 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                add(i + sum * m, (j - 1) * sum + 1, 1, a[i][j]);
            }
        }
        for (int i = 1; i <= m; i++)
            add((i - 1) * sum + 1, t, 1, 0);
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= sum; j++)
            {
                int tmp = (i - 1) * sum + j;
                ha[tmp] = j; co[tmp] = i;
            }

        }
    }
    bool dep()
    {
        queue<int> q;
        q.push(s);
        memset(depth, -1, sizeof(depth));
        depth[s] = 0;
        while (!q.empty())
        {
            int v = q.front(); q.pop();
            for (int i = st[v]; i != -1; i = arr[i].nt)
            {
                int to = arr[i].to;
                if (!arr[i].cal)
                    continue;
                if (depth[to] != -1)
                    continue;
                depth[to] = depth[v] + 1;
                q.push(to);
            }
        }
        return (depth[t] != -1);
    }
    void add(int x, int y, ll z, ll c)
    {
        top++; arr[top] = { y,st[x],top + 1,c,z }; st[x] = top;
        top++; arr[top] = { x,st[y],top - 1,-c,0 }; st[y] = top;
    }
    ll dfs(int now, ll val)
    {
        if (now == t || !val)
            return val;
        ll flow = 0;
        for (int& i = cur[now]; i != -1; i = arr[i].nt)
        {
            int to = arr[i].to;
            if (depth[to] != depth[now] + 1)
                continue;
            ll f = dfs(to, min(arr[i].cal, val));
            if (!f || !arr[i].cal)
                continue;
            flow += f;
            arr[i].cal -= f;
            arr[arr[i].rev].cal += f;
            val -= f;
            if (!val)
                return flow;
        }
        return flow;
    }
    ll dinic()
    {
        ll flow = 0;
        ll f;
        while (dep())
        {
            for (int i = 0; i <= siz; i++)
                //这里
                cur[i] = st[i];
            while (f = dfs(s, INF))
                flow += f;
        }
        return flow;
    }
    ll min_cost(ll f)
    {
        ll res = 0;

        fill(dis, dis + 1 + siz, INF);
        fill(h, h+1+siz, 0);
        priority_queue<P, vector<P>, greater<P>> q;
        dis[s] = 0;
        q.push(P(0, s));
        while (!q.empty())
        {
            P p = q.top(); q.pop();
            int v = p.second;
            if (dis[v] < p.first) continue;
            for (int i = st[v]; i != -1; i = arr[i].nt)
            {
                note& e = arr[i];
                if (e.cal > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to])
                {
                    dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                    pre[e.to] = v;
                    pree[e.to] = i;
                    q.push(P(dis[e.to], e.to));
                }
            }
        }
        if (dis[t] == INF)    return -1;
        for (int i = 0; i <= siz; i++)
            //这里改了
            h[i] += dis[i];
        ll d = f;
        //printf("2\n");
        for (int i = t; i != s; i = pre[i])
        {
            d = min(d, arr[pree[i]].cal);
            arr[pree[i]].cal -= d;;
            int rev = arr[pree[i]].rev;
            arr[rev].cal += d;
        }
    
        res += d * h[t];
        //printf("3\n");
        return res;
    }
};
edge road, new_road;
edge tmp;
int main()
{
    read();
    road.init();
    road.build(0, tn + sum * tm + 1);
    int ret = 0,ans=0;
    int n = tn, m = tm;
    while(1)
    {
        ret = road.min_cost(1);
        if (ret == -1)
            break;
        ans += ret;
        int pos = road.arr[road.pree[road.t]].rev;
        int tmp = road.arr[pos].to;
        road.add(tmp + 1, road.t, 1, 0);
        for (int i = 1; i <= n; i++)
        {
            road.add(i + m * sum, tmp + 1, 1, a[i][co[tmp]] * (ha[tmp] + 1));
        }

    }
    printf("%d", ans);
    return 0;
}