http://www.lydsy.com/JudgeOnline/problem.php?id=2879
费用流。
我们发现，每个厨师做的倒数第k道菜对总等待时间的贡献为k*做这道菜的时间。
将每个厨师拆成P个点，第i个第表示这个厨师做倒数第i道菜。
设Vi,j表示第i个厨师做第j道菜的点。
Ui表示第i道菜。
构图：
S->Vi,j一条流量为1，费用为0的边；
Vi,j->Uk一条流量为1，费用为j*t[k][i]的边；
Ui->T一条流量为p[i]，费用为0的边。
但是数据范围比较大，我们可以动态加边。
友情题：SDOI2007修车
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define re(i,a,b) for(i=a;i<=b;i++) #define red(i,a,b) for(i=a;i>=b;i--) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-9; inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); inline int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } inline LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const int maxN=40; const int maxM=100; const int maxP=800; const int INF=1<<30; int N,M,P; int p[maxN+10]; int t[maxN+10][maxM+10]; int S,T,now,first[maxN+maxM*maxP+100]; struct Tedge{int u,v,flow,cost,next;}edge[2*(maxN+maxN*maxM*maxP+maxP*maxM)+10000]; inline void addedge(int u,int v,int flow,int cost) { now++; edge[now].u=u; edge[now].v=v; edge[now].flow=flow; edge[now].cost=cost; edge[now].next=first[u]; first[u]=now; } inline void insert(int u,int v,int flow,int cost){addedge(u,v,flow,cost);addedge(v,u,0,-cost);} int head,tail,que[maxN+maxM*maxP+100]; int vis[maxN+maxM*maxP+100],dis[maxN+maxM*maxP+100],fromedge[maxN+maxM*maxP+100]; inline int SPFA() { int i; re(i,0,N+P*M+1)vis[i]=0,dis[i]=INF,fromedge[i]=-1; dis[que[0]=S]=0; head=0;tail=1; vis[S]=1; while(head!=tail) { int u=que[head++],v,flow,cost;if(head==T)head=0; vis[u]=0; for(i=first[u],v=edge[i].v,flow=edge[i].flow,cost=edge[i].cost;i!=-1;i=edge[i].next,v=edge[i].v,flow=edge[i].flow,cost=edge[i].cost) if(flow>0 && dis[u]+cost<dis[v]) { dis[v]=dis[u]+cost; fromedge[v]=i; if(!vis[v]) { vis[que[tail]=v]=1; if(dis[que[tail]]<dis[que[head]])swap(que[head],que[tail]); tail++;if(tail==T)tail=0; } } } return dis[T]!=INF; } inline void work(int &res) { int i,x=INF,y,a,b; for(i=fromedge[T];i!=-1;i=fromedge[edge[i].u]) { upmin(x,edge[i].flow); if(edge[i].u==S)y=edge[i].v,a=(y-1)/P+1,b=y%P+1; } for(i=fromedge[T];i!=-1;i=fromedge[edge[i].u])edge[i].flow-=x,edge[i^1].flow+=x,res+=x*edge[i].cost; re(i,1,N)insert((a-1)*P+b,P*M+i,1,b*t[i][a]); } inline int mincostmaxflow() { int res=0; while(SPFA())work(res); return res; } int main() { freopen("delicacy.in","r",stdin); freopen("delicacy.out","w",stdout); int i,j; N=gint();M=gint(); mmst(first,-1);now=-1; re(i,1,N)p[i]=gint(),P+=p[i]; re(i,1,N)re(j,1,M)t[i][j]=gint(); S=0;T=P*M+N+1; re(i,1,P*M)insert(S,i,1,0); re(i,1,N)insert(P*M+i,T,p[i],0); re(i,1,N)re(j,1,M)insert((j-1)*P+1,P*M+i,1,t[i][j]); cout<<mincostmaxflow()<<endl; return 0; }