记录编号	412395	评测结果	AAAAAAAAAA
题目名称	[NOI 2012]美食节	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	3.172 s
提交时间	2017-06-09 09:28:59	内存使用	355.16 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int N=50;
const int M=110;
const int P=810;
const int inf=0x7fffffff;
const int S=N+M*P+1;
const int T=N+M*P+2;
struct node{int qi,zhong,next,val,flow;}s[(M*P+N+P*M*N)<<2];
int adj[N+P*P+100+P],e=1;
inline int min(int a,int b){return a<b?a:b;}
inline void add(int qi,int zhong,int val,int flow)
{
	s[++e].qi=qi;s[e].zhong=zhong;
	s[e].val=val;s[e].flow=flow;
	s[e].next=adj[qi];adj[qi]=e;
}
int n,m,p[N+P*P+100+P];//int a[N+P*P+100+P];
int sum,dis[N+P*P+100+P],val[N][M];
bool vis[N+P*P+100+P];LL ans;
queue<int>q;
inline bool spfa()
{
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));int tmp=dis[1];
	dis[S]=0;vis[S]=1;p[S]=0;q.push(S);
	//a[S]=inf;
	while(!q.empty())
	{
		int rt=q.front();//printf("%d %d\n",rt,dis[rt]);
		vis[rt]=0;q.pop();
		for(int i=adj[rt];i;i=s[i].next)
		{
			int u=s[i].zhong;
			if(s[i].flow&&dis[u]>dis[rt]+s[i].val)
			{
				dis[u]=dis[rt]+s[i].val;p[u]=i;
				if(!vis[u])q.push(u),vis[u]=1;
			}
		}
	}
	//printf("%d\n",dis[T]);
	if(dis[T]==tmp)return 0;
	ans+=dis[T];
	int u=T,f=inf,a,b;
	while(u!=S)
	{
		f=min(s[p[u]].flow,f);
		u=s[p[u]].qi;
	}
	u=T;
	while(u!=S)
	{
		s[p[u]].flow-=f;
		s[p[u]^1].flow+=f;
		u=s[p[u]].qi;
	}
	tmp=s[p[T]].qi;
	a=tmp/sum,b=tmp%sum;
	//printf("%d %d %d\n",tmp,a,b);
	for(int j=1;j<=n;j++)//动态加边 
	//{
		//printf("%d %d %d\n",j,(a+1)*sum+b,val[j][b]*(1+a));
		add(j,(a+1)*sum+b,val[j][b]*(1+a),1),add((a+1)*sum+b,j,-(a+1)*val[j][b],0);
	//}
	add((a+1)*sum+b,T,0,1),add(T,(a+1)*sum+b,0,0);
	return 1;
}
int main()
{
	//freopen("Lex.txt","r",stdin);
	freopen("noi12_delicacy.in","r",stdin);
	freopen("noi12_delicacy.out","w",stdout);
	scanf("%d%d",&n,&m);int b;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b);sum+=b;
		add(S,i,0,b),add(i,S,0,0);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&val[i][j]);
	for(int j=1;j<=m;j++)
		add(sum+j,T,0,1),add(T,sum+j,0,0);
	for(int k=1;k<=n;k++)
		for(int j=1;j<=m;j++)
		//{
			//printf("%d %d %d\n",k,sum+j,val[k][j]);
			add(k,sum+j,val[k][j],1),add(sum+j,k,-val[k][j],0);
		//}
	while(spfa());
	printf("%lld",ans);
}