2879: [Noi2012]美食节
http://www.lydsy.com/JudgeOnline/problem.php?id=2879
RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
380608 | Liu_Ts | 2879 | Accepted | 5536 kb | 4296 ms | C++ | 1539 B | 2013-03-31 14:48:33 |
题意
有n道菜,每道菜需要p[i]份,m个厨师,第j个厨师做第i到菜需要时间t[i][j],求做完所有菜,所有人等待的最小总时间。
题解
和之前有个usaco一样,
令Sp=Σp[i]
把每个厨师拆成Sp个点,
每道菜向一个点连边,费用为这个厨师倒数第p道做这个菜,对所有人产生的影响,即p*t[i][j];(会对当前这个人以及厨师接下来所做菜的几个人产生影响)
但是这道题范围太大,
所以动态加边,
每次增广完后,找到一个当前还没有被增广的厨师,拆n个点,继续增广。
具体看程序理解。
#include<cstring> #include<cstdio> using namespace std; const int N=1000,M=100000; int u[M],v[M],w[M],c[M],next[M],head[N],k=1; int n,m,q[M],d[N],pre[N],sp,p[41],t[41][101],cnt[101],last[101]; bool vis[N]; void add(int x,int y,int z,int zz) { u[++k]=x;v[k]=y;w[k]=z;c[k]=zz;next[k]=head[x];head[x]=k; u[++k]=y;v[k]=x;w[k]=0;c[k]=-zz;next[k]=head[y];head[y]=k; } void spfa(int s,int t) { memset(d,127,sizeof(d)); d[s]=0;vis[s]=true; int l=0,r=1;q[r]=s; while(l<r) { l=l%M+1; for(int i=head[q[l]];i;i=next[i]) if(w[i]&&d[v[i]]>d[u[i]]+c[i]) { d[v[i]]=d[u[i]]+c[i];pre[v[i]]=i; if(!vis[v[i]]) { vis[v[i]]=true; r=r%M+1;q[r]=v[i]; } } vis[q[l]]=false; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",p+i); sp+=p[i]; } int S=n+m+sp+1,T=S+1; for(int i=1;i<=n;i++) { add(S,i,p[i],0); for(int j=1;j<=m;j++) { scanf("%d",&t[i][j]); add(i,n+j,1,t[i][j]); } } for(int i=1;i<=m;i++) { cnt[i]=1; add(n+i,T,1,0); last[i]=k; } int ans=0; for(;sp;sp--) { spfa(S,T);ans+=d[T]; for(int i=T;i!=S;i=u[pre[i]]) w[pre[i]]--,w[pre[i]^1]++; int j; for(j=1;j<=m&&w[last[j]-1];j++); cnt[j]++; for(int i=1;i<=n;i++) add(i,n+m+sp,1,t[i][j]*cnt[j]); add(n+m+sp,T,1,0); last[j]=k; } printf("%d\n",ans); }
2024年2月22日 18:34
Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subjec