1772: [Usaco2009 Nov]rescue 拯救奶牛貝希
1822: [JSOI2010]Frozen Nova 冷冻波

2879: [Noi2012]美食节

高橋直樹 posted @ 2013年3月31日 15:11 in BZOJ with tags bzoj NOI , 1895 阅读

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);
}
seo service london 说:
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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter