记录编号	360738	评测结果	AAAAAAAAAA
题目名称	[NOI 2012]美食节	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.469 s
提交时间	2016-12-31 16:26:49	内存使用	236.44 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010,M=1e7+10,V=1e5+10;
struct edge{
	int f,t,g,l,o;
	edge(int F=0,int T=0,int G=0,int L=0,int O=0){
		f=F;t=T;g=G;l=L;o=O;
	}
}w[M];
int head[V],next[M],tail[V];
void add(int f,int t,int g,int l){
	static int cnt=0;
	cnt++;w[cnt]=edge(f,t,g,l,cnt+1);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	cnt++;w[cnt]=edge(t,f,0,-l,cnt-1);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int n,m,p[N],sum,t[N][N],S,T,ans;
bool vis[N][N];
int P(int x,int y){//第x个厨师,倒数第y道菜 
	return (x-1)*sum+y;
}
void add_point(int x,int y){//第x个厨师,倒数第y道菜 
	if (y>sum||vis[x][y]) return;
	int pos=P(x,y);
	vis[x][y]=1;
	for (int i=1;i<=n;i++) add(sum*m+i,pos,1,y*t[i][x]);
	add(pos,T,1,0);
}
int dis[V],flow[V],from[V],color[V];
bool inque[V];
queue<int> Q;
void visit(int x,int C){
	if (color[x]!=C)
		color[x]=C,dis[x]=1e9;
}
bool spfa(){
	static int C=0;C++;//动态清空数组的染色标记 
	visit(S,C);dis[S]=0;flow[S]=1e9;
	Q.push(S);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inque[v]=0;
		for (int i=head[v];i;i=next[i]){
			int u=w[i].t;
			visit(u,C);
			if (w[i].g&&dis[u]>dis[v]+w[i].l){
				dis[u]=dis[v]+w[i].l;
				flow[u]=min(flow[v],w[i].g);
				from[u]=i;
				if (!inque[u]) Q.push(u),inque[u]=1;
			}
		}
	}
	visit(T,C);
	if (dis[T]==1e9) return 0;
	int df=flow[T];ans+=df*dis[T];
	for (int i=from[T];i;i=from[w[i].f]){
		w[i].g-=df;
		w[w[i].o].g+=df;
		if (w[i].f&&w[i].f<=sum*m){
			int x=(w[i].f-1)/sum+1,y=w[i].f-(x-1)*sum;
			add_point(x,y+1);
		}
	}
	return 1;
}
int main()
{
	freopen("noi12_delicacy.in","r",stdin);
	freopen("noi12_delicacy.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]),sum+=p[i];
	S=0;T=sum*m+n+1;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		scanf("%d",&t[i][j]);
	for (int i=1;i<=n;i++) add(S,sum*m+i,p[i],0);
	for (int i=1;i<=m;i++) add_point(i,1);
	while (spfa());
	printf("%d\n",ans);
	return 0;
}