记录编号	462775	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-10-23 07:45:04	内存使用	0.33 MiB

# include <stdio.h>
# include <string.h>
# include <algorithm>
# define maxn 105
# define inf 0x7fffffff
using namespace std;
int n,map[maxn][maxn],ans,tot,dis[105],q[105],h,t;
bool bfs(){
	 memset(dis,0xff,sizeof dis);
	 dis[1]=0,h=0,t=1,q[t]=1;
	 while(h<t){
	 	   int k=q[++h];
	 	   for(int i=1;i<=n;i++)
	 	   	   if(dis[i]<0&&map[k][i]>0){
	 	   	   	  dis[i]=dis[k]+1;
	 	   	      q[++t]=i;
	 	   	   }
	 }
	 if(dis[n]>0) return true;
	 else return false;
}
int dfs(int x,int las){
    int a=0;
	if(x==n) return las;
    for(int i=1;i<=n;i++)
    	if(map[x][i]>0&&dis[i]==dis[x]+1&&(a=dfs(i,min(las,map[x][i])))){
    	   map[x][i]-=a;
    	   map[i][x]+=a;
    	   return a;
    	}
    return 0;
}
int main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]);
	while(bfs()) while(tot=dfs(1,inf)) ans+=tot;
    printf("%d",ans);
}