做网站克隆,网站建设企业建站要求,动漫设计与制作课程,爱心建站网正题
题目链接:https://www.luogu.com.cn/problem/P2050 题目大意 nnn个菜品mmm个厨师#xff0c;第iii种菜需要pip_ipi份#xff0c;第iii个人做第jjj道菜需要时间ti,jt_{i,j}ti,j#xff0c;求最少等待时间和。 解题思路
这题和之前修车很像#xff0c;数据变大了。…正题
题目链接:https://www.luogu.com.cn/problem/P2050 题目大意
nnn个菜品mmm个厨师第iii种菜需要pip_ipi份第iii个人做第jjj道菜需要时间ti,jt_{i,j}ti,j求最少等待时间和。 解题思路
这题和之前修车很像数据变大了。
考虑网络流如果一个厨师总共要做kkk个菜那么第iii个菜的时间贡献就是(k−i1)∗t(k-i1)*t(k−i1)∗t反过来看做倒数第iii道菜的时间贡献就是i∗ti*ti∗t。
也就是如果目前厨师要做kkk道菜那么在最开头加入一个新菜时需要增加的时间就是(k1)∗t(k1)*t(k1)∗t。
定义点阵(i,j)(i,j)(i,j)表示第iii个厨师做到第jjj道菜然后和顾客构建二分图联向第jjj道菜的费用乘上jjj即可因为是最小费用所以肯定会优先把小费用的边流掉。
这样正确性已经保证但是空间复杂度显然不行。考虑动态连边因为肯定会先流小费用所以当小费用的有流时在动态加入更大费用的一条边即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define p1(x,y) (((x)-1)*K(y))
#define p2(x) (p1(m,K)(x))
using namespace std;
const int N1e510;
struct node{int to,next,w,c;
}a[N*70];
int n,m,ans,tot1,s,t,K;
int e[50][110],k[50];
int ls[N],f[N],mf[N],pre[N],mark[N];
bool v[N];
queueint q;
void addl(int x,int y,int w,int c){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;return;
}
bool SPFA(){memset(f,0x3f,sizeof(f));f[s]0;q.push(s);v[s]1;mf[s]2147483647;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(a[i].wf[x]a[i].cf[y]){f[y]f[x]a[i].c;mf[y]min(mf[x],a[i].w);pre[y]i;if(!v[y]){v[y]1;q.push(y);}}}v[x]0;}return f[t]2147483647/3;
}
void updata(){int xt;while(x!s){a[pre[x]].w-mf[t];a[pre[x]^1].wmf[t];if(xt(a[pre[x]^1].to%K)0){int ya[pre[x]^1].to;int cy%K1,posmark[y];for(int i1;in;i)addl(p2(i),p1(pos,c),1,e[i][pos]*c);addl(p1(pos,c),t,1,0);mark[p1(pos,c)]pos;}xa[pre[x]^1].to;}ansmf[t]*f[t];
}
void net_flow(){while(SPFA())updata();
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,k[i]),Kk[i];for(int i1;in;i)for(int j1;jm;j)scanf(%d,e[i][j]);sp2(n)1;ts1;for(int i1;in;i)addl(s,p2(i),k[i],0),mark[p2(i)]i;for(int i1;im;i){for(int j1;jn;j)addl(p2(j),p1(i,1),1,e[j][i]);addl(p1(i,1),t,1,0);mark[p1(i,1)]i;}net_flow();printf(%d,ans);
}
