高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=2879

题意

有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);
}