BZOJ2879 [NOI2012] 美食节

Description

CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节共有n种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有m个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: 虽然这m个厨师都会制作全部的n种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用1, 2, …, n依次编号，厨师用1, 2, …, m依次编号，将第j个厨师制作第i种菜品的时间记为 ti,j 。小M认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第k道菜，则他的等待时间就是这个厨师制作前k道菜的时间之和。而总等待时间为所有同学的等待时间之和。现在，小M找到了所有同学的点菜信息: 有 pi 个同学点了第i种菜品（i=1, 2, …, n）。他想知道的是最小的总等待时间是多少。

Input

输入文件的第1行包含两个正整数n和m，表示菜品的种数和厨师的数量。 第2行包含n个正整数，其中第i个数为pi，表示点第i种菜品的人数。 接下来有n行，每行包含m个非负整数，这n行中的第i行的第j个数为ti,j，表示第j个厨师制作第i种菜品所需的时间。 输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。

Output

输出仅一行包含一个整数，为总等待时间的最小值。

Sample Input

3 2

3 1 1

5 7

3 6

8 9

Sample Output

47

样例说明

厨师1先制作1份菜品2，再制作2份菜品1。点这3道菜的3个同学的等待时间分别为3，3+5=8，3+5+5=13。
厨师2先制作1份菜品1，再制作1份菜品3。点这2道菜的2个同学的等待时间分别为7，7+9=16。
总等待时间为3+8+13+7+16=47。
虽然菜品1和菜品3由厨师1制作更快，如果这些菜品都由厨师1制作，总等待时间反而更长。如果按上述的做法，将1份菜品1和1份菜品3调整到厨师2制作，这样厨师2不会闲着，总等待时间更短。
可以证明，没有更优的点餐方案。

数据规模及约定

对于100%的数据，n <= 40, m <= 100, p <= 800, ti,j <= 1000（其中p = ∑pi，即点菜同学的总人数）。

题意：
  n种菜m个厨师，第j个厨师做第i个菜要t[i][j]秒，每个菜点了ai份，顾客等待时间为从开始到他这份菜做完的时间，问等待总时间是多少。

思路：
  与「BZOJ1070」[SCOI2007]修车类似，只是数据规模增大了。
  因而，需要用到动态加点的思想。就是说，在我考虑下一个让谁做哪种的菜的时候，它只会是某一位厨师的倒数的第x道菜，因为如果让他把这道菜放在倒数第x+1道菜来做的话，肯定没有放在倒数第x道菜更优。因而，只有当一位厨师做了倒数第x道菜后（该厨师的倒数第x位置有了流量后），才允许他做倒数第x+1道菜（在菜与该厨师的倒数第x+1位置之间连边）。其他和BZOJ1070相似。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+20;
const int INF = 1e9+7;
typedef long long ll;
//建边的时候建错了，以及要避免变量的重名，MCMF中的n，m不是题目给的n，m的意思 
//cai是菜数，cook是厨师数，people是顾客数，sp=spend
int cai,cook,sp[50][110],people;
struct MCMF{
    struct Edge{
        int from,to,cap,cost;
        Edge(){}
        Edge(int from,int to,int cap,int cost):from(from),to(to),cap(cap),cost(cost){}
    };
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn];//inqueue
    int d[maxn];//dis
    int p[maxn];//pre
    int a[maxn];//flow
    void init()
    {
        for(int i=0;i<=n;++i) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost)
    {
        edges.push_back(Edge(from,to,cap,cost));
        edges.push_back(Edge(to,from,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BF(int& flow,int& cost)
    {
        for(int i=1;i<=n;++i) d[i]=INF,inq[i]=0;
        d[s]=0,inq[s]=1,p[s]=0,a[s]=INF;
        queue<int> Q;
        Q.push(s);
        while(!Q.empty())
        {
            int u=Q.front();Q.pop();
            inq[u]=0;
            //cout<<u<<' '<<G[u].size()<<' '<<d[u]<<'\n';
            for(int i=0;i<G[u].size();++i)
            {
                Edge& e=edges[G[u][i]];
                if(e.cap&&d[e.to]>d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap);
                    if(!inq[e.to])
                    {
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]==INF) return false;
        flow+=a[t];
        cost+=d[t]*a[t];
        int u=t;
        while(u!=s)
        {
            edges[p[u]].cap-=a[t];
            edges[p[u]^1].cap+=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }
    int Mincost()
    {
        int flow=0,cost=0;
        //cout<<m<<endl;
        while(BF(flow,cost))
        {
            int x=edges[p[t]].from,y=(x-cai)/people+1,z=(x-cai)%people;
            AddEdge(x+1,t,1,0);
            for(int i=1;i<=cai;++i) AddEdge(i,x+1,1,((z+1)*sp[i][y]));
            //cout<<edges[p[t]].from<<' '<<flow<<' '<<cost<<endl;
            //cout<<m<<endl;
        }
        //for(int i=1;i<=10;++i) cout<<i<<' '<<p[i]<<endl;
        return cost;
    }
}NF;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        //if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}

inline void readin()
{
    int temp;
    cai=read(),cook=read();
    for(int i=1;i<=cai;++i)
    {
        temp=read();
        NF.AddEdge(0,i,temp,0);
        people+=temp;
    }
    NF.s=0;
    NF.n=NF.t=cai+people*cook+1;
    for(int i=1;i<=cai;++i) for(int j=1;j<=cook;++j)
    {
        sp[i][j]=read();
        NF.AddEdge(i,cai+(j-1)*people+1,1,sp[i][j]);
    }
    for(int i=1;i<=cook;++i) NF.AddEdge(cai+(i-1)*people+1,NF.t,1,0);
}

int main()
{
    NF.init();
    readin();
    cout<<NF.Mincost();
    return 0;
}