P2050 [NOI2012] 美食节 网络流

题意：

戳这里

分析：

• 暴力：

  直接上修车的建模， (60pts) 滚粗

• 正解:

  由于这题菜品数量太多，所以有好多 (id(j,k)) 根本用不上，按照贪心的思想来说，一旦一个厨师开始做菜，他就会连续的做下去，不会中途停下，因为这样不优，所以实际上体现在网络流的模型里面，每个厨师对应的分层图的层一定是连续的，我们就可以一层一层的跑

  最开始我们只把每个菜连向每一个厨师的第一次的位置，每一层找到一个增广的路径，代表这个厨师做了第 (k) 到菜，那么我们把每个菜连向这个厨师的第 (k+1) 次的位置，表示他该做第 (k+1) 次了，这样总的点数都是 (O(m+p)) 边数是 (O(n(m+p))) 的，网络流的玄学复杂度下就过了

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
	typedef long long ll;
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 1e5+5;
	const int maxm = 1e7+5;
	const int inf = 0x3f3f3f3f;
	int cnt=1,n,m,st,ed,ans,sum;
	int head[maxn],dis[maxn],flow[maxn],pre[maxn],lst[maxn],p[maxn],t[41][101],dish[maxn],cook[maxn];
	bool vis[maxn];
	queue<int> q;
	struct edge
	{
		int to,nxt,w,cst;
	}e[maxm];
	
	inl int id(int x,int y)
	{
		return (x-1)*sum+y;
	}
	
	void add(int u,int v,int w,int x)
	{
		e[++cnt].to=v;
		e[cnt].w=w;
		e[cnt].cst=x;
		e[cnt].nxt=head[u];
		head[u]=cnt;
	}
	
	void add_edge(int u,int v,int w,int x)
	{
		add(u,v,w,x);add(v,u,0,-x);
	}
	
	bool spfa()
	{
		for(int i=st;i<=ed;i++) pre[i]=-1,flow[i]=inf,dis[i]=inf;
		dis[st]=0;q.push(st);
		while(!q.empty())
		{
			int u=q.front();q.pop();vis[u]=false;
			for(int i=head[u];i;i=e[i].nxt)
			{
				int v=e[i].to;
				if(e[i].w&&dis[v]>dis[u]+e[i].cst)
				{
					dis[v]=dis[u]+e[i].cst;
					pre[v]=u;
					lst[v]=i;
					flow[v]=min(flow[u],e[i].w);
					if(!vis[v])
					{
						vis[v]=true;
						q.push(v);
					}
				}
			}
		}
		return pre[ed]!=-1;
	}
	
	void MCMF()
	{
		while(spfa())
		{
			int pos=e[lst[ed]^1].to;
			add_edge(pos+1,ed,1,0);
			for(int i=1;i<=n;i++) add_edge(m*sum+i,pos+1,1,t[i][cook[pos]]*(dish[pos]+1));
			
			int now=ed;
			ans+=dis[ed]*flow[ed];
			while(now!=st)
			{
				e[lst[now]].w-=flow[ed];
				e[lst[now]^1].w+=flow[ed];
				now=pre[now];
			}
		}
	}
	
	void work()
	{
		n=read();m=read();
		for(int i=1;i<=n;i++) p[i]=read(),sum+=p[i];
		st=0;ed=m*sum+n+1;
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) t[i][j]=read(),add_edge(m*sum+i,id(j,1),1,t[i][j]);
		for(int j=1;j<=m;j++) for(int k=1;k<=sum;k++) cook[id(j,k)]=j,dish[id(j,k)]=k;
		for(int i=1;i<=n;i++) add_edge(st,m*sum+i,p[i],0);
		for(int j=1;j<=m;j++) add_edge(id(j,1),ed,1,0);
		MCMF();
		printf("%d
",ans);
	}

}

int main()
{
	zzc::work();
	return 0;
}