建图方式参见 SCOI 2007 修车，但这道题数据范围更大，需要动态加边：

• 由于我们跑一次最短路只能找出一次增广路，所以可以暂时不连不需要的边。
• 首先把所有厨师做倒数第 \(1\) 道菜与所有菜连边，那么找到的增广路上一定经过了一个点，设它表示第 \(i\) 个厨师做倒数第 \(1\) 道菜。
• 然后添加第 \(i\) 个厨师做倒数第 \(2\) 道菜的点，与汇点和所有菜连边，以此类推。
• 因为倒数第 \(k\) 道菜的代价一定比倒数 \(k+1\) 道菜贵，所以如果流没流向倒数第 \(k\) 道菜是不可能流向倒数第 \(k+1\) 道菜的。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 81000;
int n, m, sum, cnt, ans, p[45], a[45][105];
int head[maxn], dist[maxn], incf[maxn], pre[maxn];
bool inq[maxn];
struct edge {
    int to, cap, cost, nxt;
} e[100010];

void add_edge(int from, int to, int cap, int cost) {
    e[cnt] = (edge){to, cap, cost, head[from]}, head[from] = cnt++;
    e[cnt] = (edge){from, 0, -cost, head[to]}, head[to] = cnt++;
}

bool spfa(int s, int t) {
    fill(dist, dist + maxn, INT_MAX);
    memset(inq, 0, sizeof(inq));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    inq[s] = 1;
    incf[s] = INT_MAX;
    while (!q.empty()) {
        int v = q.front();
        inq[v] = 0;
        q.pop();
        for (int i = head[v]; i != -1; i = e[i].nxt) {
            if (e[i].cap > 0 && dist[e[i].to] > dist[v] + e[i].cost) {
                dist[e[i].to] = dist[v] + e[i].cost;
                incf[e[i].to] = min(incf[v], e[i].cap);
                pre[e[i].to] = i;
                if (!inq[e[i].to]) {
                    q.push(e[i].to);
                    inq[e[i].to] = 1;
                }
            }
        }
    }
    return dist[t] != INT_MAX;
}

void update(int s, int t) {
    int x = t;
    while (x != s) {
        int i = pre[x];
        e[i].cap -= incf[t];
        e[i ^ 1].cap += incf[t];
        x = e[i ^ 1].to;
    }
    ans += dist[t] * incf[t];
}

void edmonds_karp(int s, int t) {
    while (spfa(s, t)) {
        update(s, t);
        int x = e[pre[t] ^ 1].to;
        add_edge(x + 1, t, 1, 0);
        for (int i = 1; i <= n; i++) {
            add_edge(i + sum * m, x + 1, 1, a[i][x / sum + 1] * (x % sum + 1));
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        sum += p[i];
    }
    const int s = 0, t = n + sum * m + 1;
    for (int i = 1; i <= n; i++) {
        add_edge(s, i + sum * m, p[i], 0);
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            add_edge(i + sum * m, (j - 1) * sum + 1, 1, a[i][j]);
        }
    }
    for (int i = 1; i <= m; i++) {
        add_edge((i - 1) * sum + 1, t, 1, 0);
    }
    edmonds_karp(s, t);
    printf("%d\n", ans);
    return 0;
}

http://www.cnblogs.com/JSZX11556/p/5144807.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=520130;
const int INF=987654321;
struct Edge{
int from,to,cap,flow,cost;
};
int P[maxn],Time[45][110],tot=0,cnt[110];
vector<Edge>edges;
vector<int>G[maxn];
int n,m,s,t;
int dist[maxn],a[maxn],p[maxn];
bool inQ[maxn];
void Addedge(int from,int to,int cap,int cost){
Edge e;
e.from=from,e.to=to,e.cap=cap,e.flow=0,e.cost=cost;
edges.push_back(e);
e.from=to,e.to=from,e.cap=0,e.flow=0,e.cost=-cost;
edges.push_back(e);
int M=edges.size();
G[from].push_back(M-2);
G[to].push_back(M-1);
}
bool spfa(int &New,int &Maxflow,int &Mincost){
for(int i=s;i<=t;i++)dist[i]=INF;
memset(inQ,0,sizeof(inQ));
dist[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;
for(int i=0;i<G[u].size();i++)
{ Edge& e=edges[G[u][i]];
if(e.cap>e.flow &&dist[e.to]>dist[u]+e.cost)
{ dist[e.to]=dist[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
if(!inQ[e.to]){inQ[e.to]=1;Q.push(e.to);}
}
}
}
if(dist[t]==INF)return false;
Maxflow+=a[t];
Mincost+=dist[t]*a[t];
int u=t;
New=(edges[p[u]].from-n)/tot+1;
//cout<<"New: "<<New<<endl;
cnt[New]++;
while(u!=s)
{ edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
u=edges[p[u]].from;
}
return true;
}
int mincost(){
int Maxflow=0,Mincost=0,New;
while(spfa(New,Maxflow,Mincost))
{ for(int i=1;i<=n;i++)
Addedge(i,n+(New-1)*tot+cnt[New],1,Time[i][New]*cnt[New]);
Addedge(n+(New-1)*tot+cnt[New],t,1,0);
}
return Mincost;
}
void read_data(){
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
{ scanf("%d",&P[i]);
tot+=P[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&Time[i][j]);

}
void Build_graph(){
s=0;t=n+m*tot+1;
//cout<<"tot: "<<tot<<endl;
for(int i=1;i<=n;i++)
Addedge(s,i,P[i],0);
for(int j=1;j<=m;j++)
{Addedge(n+tot*(j-1)+1,t,1,0);
cnt[j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
Addedge(i,n+(j-1)*tot+cnt[j],1,Time[i][j]*cnt[j]);
}
int main(){
read_data();
Build_graph();
printf("%d\n",mincost());
return 0;
}

http://hi.baidu.com/macaulish64/item/a0cd34960d1ab3f57a7f01ea

加了LLL之后快了好多。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 7676 KiB, score = 10
测试数据 #1: Accepted, time = 811 ms, mem = 9208 KiB, score = 10
测试数据 #2: Accepted, time = 312 ms, mem = 8828 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 7976 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 7744 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 7924 KiB, score = 10
测试数据 #6: Accepted, time = 156 ms, mem = 8572 KiB, score = 10
测试数据 #7: Accepted, time = 514 ms, mem = 10284 KiB, score = 10
测试数据 #8: Accepted, time = 967 ms, mem = 11136 KiB, score = 10
测试数据 #9: Accepted, time = 702 ms, mem = 11136 KiB, score = 10
Accepted, time = 3523 ms, mem = 11136 KiB, score = 100

终于过了。。。冷死。。。
我是这么做的，分类讨论一下，边数多的用zkw费用流，边数少的SPFA，记得动态建图。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 7672 KiB, score = 10
测试数据 #1: Accepted, time = 1341 ms, mem = 9212 KiB, score = 10
测试数据 #2: Accepted, time = 452 ms, mem = 8828 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 7972 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 7740 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 7928 KiB, score = 10
测试数据 #6: Accepted, time = 156 ms, mem = 8568 KiB, score = 10
测试数据 #7: Accepted, time = 1279 ms, mem = 10284 KiB, score = 10
测试数据 #8: Accepted, time = 1216 ms, mem = 11140 KiB, score = 10
测试数据 #9: Accepted, time = 686 ms, mem = 11144 KiB, score = 10
Accepted, time = 5191 ms, mem = 11144 KiB, score = 100

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define MAXN 50
#define MAXM 110
#define MAXP 810
#define MAXV 100010
#define clear( x ) memset( x , 0 , sizeof( x ) )
#define inf 0x7fffffff

struct edge {
edge *next , *pair ;
int t , f , c ;
edge ( ) {
next = pair = NULL ;
}
} *head[ MAXV ] ;

void Add( int s , int t , int f ,int c ) {
edge *p = new( edge ) ;
p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ] ;
head[ s ] = p ;
}

void AddEdge( int s , int t , int f , int c ) {
Add( s , t , f , c ) , Add( t , s , 0 , - c ) ;
head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
}

int S , T , V , node[ MAXM ][ MAXP ] , w[ MAXV ][ 2 ] , last[ MAXM ] ;
bool visit[ MAXM ][ MAXP ] ;

int Time[ MAXN ][ MAXM ] , n , m , p[ MAXN ] , P = 0 ;

int cost = 0 , dist[ MAXV ] , slack[ MAXV ] ;
bool f[ MAXV ] ;

int aug( int v , int flow ) {
if ( v == T ) {
cost += dist[ S ] * flow ; return flow ;
}
if ( w[ v ][ 1 ] < P ) if ( ! visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] ) {
visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = true ;
node[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = ++ V ;
w[ V ][ 0 ] = w[ v ][ 0 ] , w[ V ][ 1 ] = w[ v ][ 1 ] + 1 ;
AddEdge( V , T , 1 , 0 ) ;
for ( int i = 0 ; i ++ < n ; ) AddEdge( i , V , 1 , Time[ i ][ w[ V ][ 0 ] ] * w[ V ][ 1 ] ) ;
dist[ V ] = 0 ; f[ V ] = true ; slack[ V ] = inf ;
}
f[ v ] = false ; int rec = 0 ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && f[ p -> t ] ) {
if ( dist[ v ] == dist[ p -> t ] + p -> c ) {
int ret = aug( p -> t , min( flow - rec , p -> f ) ) ;
p -> f -= ret , p -> pair -> f += ret ;
if ( ( rec += ret ) == flow ) return flow ;
} else slack[ p -> t ] = min( slack[ p -> t ] , dist[ p -> t ] + p -> c - dist[ v ] ) ;
}
return rec ;
}

bool relabel( ) {
int delta = inf ;
for ( int i = 0 ; i ++ < V ; ) if ( f[ i ] ) delta = min( delta , slack[ i ] ) ;
if ( delta == inf ) return false ;
for ( int i = 0 ; i ++ < V ; ) if ( ! f[ i ] ) dist[ i ] += delta ;
return true ;
}

void costflow( ) {
for ( int i = 0 ; i ++ < V ; ) dist[ i ] = 0 ;
do {
for ( int i = 0 ; i ++ < V ; ) slack[ i ] = inf ;
do {
for ( int i = 0 ; i ++ < V ; ) f[ i ] = true ;
} while ( aug( S ,inf ) ) ;
} while ( relabel( ) ) ;
}

int pre[ MAXV ] , Q[ MAXV * 10 ] ;
edge *Aug[ MAXV ] ;

void spfa( ) {
for ( int i = 0 ; i ++ < V ; ) dist[ i ] = inf , f[ i ] = false ;
int Head = 0 , tail = 0 ;
dist[ S ] = 0 , Q[ ++ tail ] = S , pre[ S ] = 0 , f[ S ] = true ;
while ( Head < tail ) {
int v = Q[ ++ Head ] ;
f[ v ] = false ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && dist[ p -> t ] > dist[ v ] + p -> c ) {
dist[ p -> t ] = dist[ v ] + p -> c ;
if ( ! f[ p -> t ] ) {
f[ p -> t ] = true ; Q[ ++ tail ] = p -> t ;
}
pre[ p -> t ] = v , Aug[ p -> t ] = p ;
}
}
}

int main( ) {
scanf( "%d%d" , &n , &m ) ;
for ( int i = 0 ; i ++ < n ; ) {
scanf( "%d" , &p[ i ] ) ; P += p[ i ] ;
}
clear( head ) ;
V = n ; S = ++ V , T = ++ V ;
for ( int i = 0 ; i ++ < n ; ) {
AddEdge( S , i , p[ i ] , 0 ) ;
}
clear( visit ) , clear( w ) ;
visit[ 0 ][ 1 ] = true ;
for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) scanf( "%d" , &Time[ i ][ j ] ) ;
for ( int i = 0 ; i ++ < m ; ) {
visit[ i ][ 1 ] = true ; node[ i ][ 1 ] = ++ V ; last[ i ] = 1 ;
w[ V ][ 0 ] = i , w[ V ][ 1 ] = 1 ;
for ( int j = 0 ; j ++ < n ; ) AddEdge( j , V , 1 , Time[ j ][ i ] ) ;
AddEdge( V , T , 1 , 0 ) ;
}
if ( ( m + P ) * n > 30000 ) costflow( ) ; else {
for ( int i = 0 ; i ++ < P ; ) {
spfa( ) ; cost += dist[ T ] ; if ( i == P ) break ;
for ( int i = T ; pre[ i ] ; i = pre[ i ] ) Aug[ i ] -> f -- , Aug[ i ] -> pair -> f ++ ;
for ( int j = 0 ; j ++ < m ; ) if ( ! head[ node[ j ][ last[ j ] ] ] -> f ) {
node[ j ][ ++ last[ j ] ] = ++ V ;
for ( int k = 0 ; k ++ < n ; ) AddEdge( k , V , 1 , Time[ k ][ j ] * last[ j ] ) ;
AddEdge( V , T , 1 , 0 ) ;
}
}
}
printf( "%d\n" , cost ) ;
return 0 ;
}