记录编号	223655	评测结果	AAAAAAAAAA
题目名称	[NOI 2012]美食节	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	2.466 s
提交时间	2016-02-12 17:38:54	内存使用	43.79 MiB

#include<cstdio>
#include<cstring>
#include<map>
std::map<int,int>mp;
int n,m,T=150,cnt=150,p[45],num[110],t[45][110];
int shu,first[210000];
struct edge{
	int u,v,w,c,nx;
}o[2100000];
inline void add(int u,int v,int w,int c){
	o[++shu].u=u,o[shu].v=v,o[shu].w=w,o[shu].c=c,o[shu].nx=first[u],first[u]=shu;
	o[++shu].u=v,o[shu].v=u,o[shu].w=-w,o[shu].c=0,o[shu].nx=first[v],first[v]=shu;
}
inline void build(){
	shu=1,memset(first,0,sizeof(first));
	for(int i=1;i<=n;++i) add(0,i,0,p[i]);
	for(int i=1;i<=n;++i) for(int j=n+1;j<=n+m;++j) add(i,j,t[i][j-n]*num[j-n],1);
	for(int i=n+1;i<=n+m;++i) mp[i]=i-n,add(i,T,0,1);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&p[i]);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&t[i][j]);
	for(int i=1;i<=m;++i) num[i]=1;
	build();
}
bool flag[210000];
int ans,u,l,r,q[210000],d[210000],pre[210000];
inline bool spfa(){
	memset(d,0x3f,sizeof(d));
	q[l=r=0]=0,d[0]=0;
	while(l<=r){
		u=q[l++],flag[u]=0;
		for(int i=first[u];i;i=o[i].nx)
		    if(o[i].c&&d[o[i].v]>d[u]+o[i].w){
				d[o[i].v]=d[u]+o[i].w,pre[o[i].v]=i;
				if(!flag[o[i].v]){
					q[++r]=o[i].v;
					flag[o[i].v]=1;
				}
		    }
	}
	if(d[T]>1e9) return 0;
	return 1;
}
inline void dfs(){
	int i=T,now=0;
	while(i){
		--o[pre[i]].c,++o[pre[i]^1].c,i=o[pre[i]].u;
		if(mp[i]&&!now)
		    now=mp[i];
	}
	mp[++cnt]=now;
	++num[now];
	add(cnt,T,0,1);
	for(int i=1;i<=n;++i)
	    add(i,cnt,t[i][now]*num[now],1);
}
int main(){
	freopen("noi12_delicacy.in","r",stdin);
	freopen("noi12_delicacy.out","w",stdout);
	init();
	while(spfa())
		ans+=d[T],dfs();
	printf("%d",ans);
}