记录编号	149071	评测结果	AAAAAAAAA
题目名称	[网络流24题] 分配问题	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-02-18 14:41:49	内存使用	0.87 MiB

#include<cstdio>
#include<cstring>
char ch[100000],*ptr=ch;
const int inf=0x3f3f3f3f;
bool vis[205],cap[25000];
int to[25000],next[25000],cost[25000],path[25000];
int n,en,ans,len=1,g[205],pre[205],dis[205],q[20000];
void in(int &x){
	x=0;while(*ptr<48) ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
}
void add(int x,int y,int w){
	to[++len]=y,next[len]=g[x],cap[len]=1,cost[len]=w,g[x]=len;
	to[++len]=x,next[len]=g[y],cap[len]=0,cost[len]=-w,g[y]=len;
}
bool spfa(){
	int l=1,r=1;
	memset(dis,0x3f,sizeof dis);
	q[1]=0,dis[0]=0;
	while(l<=r){
		int x=q[l++];vis[x]=0;
		for(int i=g[x];i;i=next[i]){
			if(dis[to[i]]>dis[x]+cost[i]&&cap[i]){
				dis[to[i]]=dis[x]+cost[i],pre[to[i]]=x,path[to[i]]=i;
				if(!vis[to[i]]) q[++r]=to[i],vis[to[i]]=1;
			}
		}
	}
	if(dis[en]==inf) return 0;
	for(int i=en;i;i=pre[i]){
		cap[path[i]]=0;
		cap[path[i]^1]=1;
	}
	return ans+=dis[en],1;
}
int main(){
	freopen("job.in","r",stdin);
	freopen("job.out","w",stdout);
	fread(ch,1,100000,stdin);
	in(n),en=n<<1|1;
	for(int k,i=1;i<=n;i++){
		add(0,i,0),add(i+n,en,0);
		for(int j=1;j<=n;j++) in(k),add(i,j+n,k);
	}
	while(spfa());
	printf("%d\n",ans),ans=0;
	for(int i=2;i<=len;i++) {
		if(i&1) cap[i]=0;
		else cap[i]=1; 
		cost[i]=-cost[i];
	}
	while(spfa());
	printf("%d",-ans);
}