看一眼，这不是修车原题吗？
把厨师拆成 $n*m$ 个点，第 $k$ 种菜连向第 $i$ 个厨师的第 $j$ 个点表示第 $i$ 个厨师倒数做的第 $j$ 个菜是 $k$
可以发现厨师 $i$ 做的倒数第 $j$ 个菜的贡献是 $j*time[i][j]$ （$time[i][j]$ 表示厨师 $i$ 做第 $j$ 种菜需要的时间）
连边 $(S,k,num[k],0)$ 表示第 $k$ 种菜要做 $num[k]$ 个
连边 $(k,cooker[i][j],1,j*time[i][k])$ 表示第 $k$ 种菜给厨师 $i$ 留到倒数第 $j$ 个做，需要的时间就是 $j*tim[i][k]$
连边 $(cooker[i][j],T,1,0)$ 表示厨师不能同时做好几种菜
然后跑最小费用最大流
然后 $T$ 成 $60$ 分...
考虑优化，发现费用流时的时间主要耗在玄学的 $SPFA$ 上了，发现 $SPFA$ 的复杂度和边数有很大关系
考虑删掉没用的边
但是，好像每一条边都有用...
考虑一下费用流的过程，每次只找一条增广路，并且显然厨师一定不会闲着（不会出现第 $i$ 个位置没有流，第 $i+1$ 个位置有流）
所以我们可以动态地加边，每次找完一条增广路后再加可能会用到的边
具体看代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; 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*f; } const int N=1e5+7,M=1e7+7,INF=1e9+7; int fir[N],from[M],to[M],val[M],cst[M],cntt=1; inline void add(int a,int b,int c,int d) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; cst[cntt]=d; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; cst[cntt]=-d; } int dis[N],mif[N],pre[N],S,T; queue <int> q; bool inq[N]; bool SPFA() { for(int i=S;i<=T;i++) dis[i]=INF; q.push(S); inq[S]=1; dis[S]=0,mif[S]=INF; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!val[i]||dis[v]<=dis[x]+cst[i]) continue; dis[v]=dis[x]+cst[i]; pre[v]=i; mif[v]=min(mif[x],val[i]); if(!inq[v]) q.push(v),inq[v]=1; } } return dis[T]<INF; } int n,m,p[2007][2007],tot;//p[i][j]表示第i种菜给第j个厨师需要的时间 ll ans; void upd() { for(int now=T,i=pre[T]; now!=S; now=to[i^1],i=pre[now]) val[i]-=mif[T],val[i^1]+=mif[T]; ans+=1ll*mif[T]*dis[T]; int v=to[pre[T]^1],u=(v-n-1)/tot+1,t=(v-n)%tot;//u存厨师，t存此时是倒数第几个做的菜 add(v+1,T,1,0);//向厨师的下一个点连边 for(int i=1;i<=n;i++) add(i,v+1,1,p[i][u]*(t+1));//每个菜都可以让此厨师做 } int main() { n=read(),m=read(); int a; for(int i=1;i<=n;i++) a=read(),add(S,i,a,0),tot+=a; S=0,T=n+m*tot+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { p[i][j]=read(); add(i,n+(j-1)*tot+1,1,p[i][j]); }//初始边 for(int i=1;i<=m;i++) add(n+(i-1)*tot+1,T,1,0);//初始边 while(SPFA()) upd(); printf("%lld",ans); return 0; }