记录编号	281630	评测结果	AAAAAAAAAA
题目名称	[NOI 2012]美食节	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	5.189 s
提交时间	2016-07-11 22:21:55	内存使用	158.70 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=1000000000;
const int maxn=100010,maxm=10000010;
int cnt=1,fir[maxn],nxt[maxm],to[maxm];
int cap[maxm],val[maxm],dis[maxn],path[maxn];

void add(int a,int b,int c,int v){
    nxt[++cnt]=fir[a];to[cnt]=b;
    cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
}
void addedge(int a,int b,int c,int v){
    add(a,b,c,v);
    add(b,a,0,-v);
}

int S,T;
int vis[maxn];
int Spfa(){
    deque<int>q;
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push_front(S);
    dis[S]=0;vis[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop_front();vis[x]=0;
        for(int i=fir[x];i;i=nxt[i])
            if(cap[i]&&dis[x]+val[i]<dis[to[i]]){
                dis[to[i]]=val[i]+dis[x];
                path[to[i]]=i;
                if(vis[to[i]])continue;
                if(dis[to[i]]<dis[x])
					q.push_front(to[i]);
				else
					q.push_back(to[i]);
				vis[to[i]]=1;	
            }
    }
    return dis[T]==dis[T+1]?0:dis[T]; 
}

int pos;
int Aug(){
    int p=T,f=INF;
    while(p!=S){
        f=min(f,cap[path[p]]);
        if(to[path[p]^1]==S)
        	pos=p;
        p=to[path[p]^1];
    }
    p=T;
    while(p!=S){
        cap[path[p]]-=f;
        cap[path[p]^1]+=f;
        p=to[path[p]^1];
    }
    return f;
}

int n,m,P,p[maxn];
int a[1010][1010];
int MCMF(){
    int ret=0,d,x,y;
    while(d=Spfa()){
        ret+=Aug()*d;
    	x=(pos-1)/m+1;
    	y=(pos-1)%m+1;
    	for(int k=1;k<=n;k++)
			addedge(x*m+y,P*m+k,1,(x+1)*a[k][y]);
	}
    return ret;    
}


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]);	
		P+=p[i];
	}
	S=0;T=P*m+n+1;
	for(int i=1;i<=P*m;i++)
		addedge(S,i,1,0);
	for(int i=P*m+1;i<=P*m+n;i++)
		addedge(i,T,p[i-P*m],0);
		
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	
	for(int j=1;j<=m;j++)
		for(int k=1;k<=n;k++)
			addedge(j,P*m+k,1,a[k][j]);
			
	printf("%d\n",MCMF());
	return 0;
}