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

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int MAXN = 1000005,MAXN_edge = 10000005;
const int inf = 0x3f3f3f3f;
int n,m,w[105][105],num[45],s,t;
int first[MAXN],e=2,dis[MAXN],tot,pre[MAXN];
int flow[MAXN];
int ans = 0;
bool vis[MAXN];


struct edge{
    int u,v,next,w,c;
}a[MAXN_edge];

inline void add(int u,int v,int w,int c){
    a[e].u=u;
    a[e].v=v;
    a[e].w=w;
    a[e].c=c;
    a[e].next=first[u];
    first[u]=e++;
}

inline void push(int u,int v,int w,int c){
    add(u,v,w,c);add(v,u,0,-c);
}

inline bool bfs(){
    memset(flow,0x3f,sizeof(flow));
    memset(dis,0x3f,sizeof(dis));
    memset(pre,0,sizeof(pre));
    dis[s]=0;
    vis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int k=q.front();
        q.pop();vis[k]=0;
        for(int i=first[k];i;i=a[i].next){
            int v=a[i].v;
            if(dis[v]>dis[k]+a[i].c && a[i].w){
                dis[v]=dis[k]+a[i].c;
                pre[v]=i;
                flow[v]=min(flow[k],a[i].w);
                if(!vis[v])vis[v]=1,q.push(v);
            }
        }
    }
    return dis[t]!=0x3f3f3f3f;
}

inline void change(){
    ans+=dis[t]*flow[t];
    for(int i=pre[t];i;i=pre[a[i].u]){
    	a[i].w-=flow[t];
    	a[i^1].w+=flow[t];
	}
    int p = a[pre[t]].u/tot,b=a[pre[t]].u%tot;
    for(int i=1;i<=n;i++)
        push(i,(1+p)*tot+b,1,w[b][i]*(p+1));
    push((1+p)*tot+b,t,1,0);
}


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",&num[i]),tot+=num[i];
    
    t=tot*tot+tot+1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&w[j][i]);

    for(int i=1;i<=n;i++) push(s,i,num[i],0);
    
    for(int i=1;i<=m;i++)push(tot+i,t,1,0);

    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++){
            push(i,tot+k,1,w[k][i]);
		}
        
	while(bfs())change();
    
    printf("%d\n",ans);
}