本文共 2625 字，大约阅读时间需要 8 分钟。
费用流。
我们发现，每个厨师做的倒数第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的边。
但是数据范围比较大，我们可以动态加边。
友情题：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include 适用于CF,UOJ，但不适用于poj using namespace std;typedef long long LL;typedef double DB;typedef pair PII;typedef complex 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 inline T sqr(T x){ return x*x;}template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;}template inline void upmax(T &t,T tmp){ if(t 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
转载于:https://www.cnblogs.com/maijing/p/4693592.html
