每日归档： 2019年2月6日

这一题是SCOI2007修车的威力加强版。
用常规的写法显然是无法通过的。
我们考虑动态加边。
这样就可以最小化每一次松弛带来的影响，于是复杂度就变成了O(能过)
（才怪呢。我卡常卡了半天结果还是开了O2才过。）
（赶紧学zkw费用流）

#include<iostream>
#include<cstdio>
#include<queue>
#define calc(I,J) ((J-1)*sm+I)
#define calc2(I) (I+sm*m)

namespace IO{
	const int S = 1E6;
	char buf[S];
	int len=0,pos=0;
	inline char frc(){
		if(len==pos){pos=0,len=fread(buf,1,S,stdin);}
		if(len==pos){exit(0);}else{putchar(buf[pos]);return buf[pos++];};
	}
	inline int fri(){
		int fr=1,ch=frc(),x=0;
		while(ch<=32)ch=frc();
		if(ch=='-')fr=-1,ch=frc();
		while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=frc();
		putchar(ch);
		return x*fr;
	}
}

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[6600005];
int h[90005],et=-1;

inline void add(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
	e[++et]=(ee){U,0,-C,h[V]};
	h[V]=et;
}
//mp[i][j]表示第i种菜由第j名厨师做需要消耗的时间。 
int n,m,s,t,sm,vis[90005],dis[90005],val[90005],fa[90005],nw[90005],po[45],mp[45][105];
int q[90005];
int l,r;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	l=1,r=0;
	q[++r]=s;
	register int p;
	while(l<=r){
		p=q[l++];
		vis[p]=0;
		for(register int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q[++r]=e[i].v;
				}
			}
		}
	}
	return fa[t]!=-1;
}
//倒数第I个，厨师J 
int ans;
inline void EK(){
	register int p,cnt,ck;
	while(SPFA()){
		cnt=fa[t]%sm,ck=fa[t]/sm+1;
		++cnt;
		//注意这里的逆hash 
		for(int i=1;i<=n;++i){
			add(calc2(i),calc(cnt,ck),1,cnt*mp[i][ck]);
		}
		p=t;
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
void init(){
	puts("2333");
	n=IO::fri(),m=IO::fri();
	for(int i=1;i<=n;++i){
		po[i]=IO::fri();
		sm+=po[i];
	}
	s=sm*m+n+1,t=sm*m+n+2;
	for(register int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			mp[i][j]=IO::fri();
			add(calc2(i),calc(1,j),1,mp[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		add(s,calc2(i),po[i],0);
	}
	for(register int i=1;i<=sm*m;++i){
		add(i,t,1,0);
	}
	EK();
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}