记录编号	581445	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-03 09:51:09	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 110,M = 20010;
int n;
struct made{
    int ver,ed,nx;
}e[M];;
int hd[N],tot,v[N],fa[N],incf[N];
int maxflow; 
void add_(int x,int y,int z){
    tot++;
    e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
    tot++;
    e[tot].ver = x,e[tot].ed = 0,e[tot].nx = hd[y],hd[y] = tot;
    return;
}
bool bfs(){
    memset(v,0,sizeof(v));
    queue<int>q;
    v[1] = 1;
    q.push(1);
    incf[1] = 1 << 29;
    while(!q.empty()){
        int x = q.front();q.pop();
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver,z = e[i].ed;
            if(z > 0){
                if(v[y])continue;
                incf[y] = min(incf[x],z);
                fa[y] = i;
                q.push(y);v[y] = 1;
                if(y == n)return 1;
            }
        }
    }
    return 0;
}
void update(){
    int x = n;
    while(x != 1){
        int i = fa[x];
        e[i].ed -= incf[n];
        e[i^1].ed += incf[n];
        x = e[i^1].ver;
    }
    maxflow += incf[n];
    return;
}
int main(){
    freopen("maxflowa.in","r",stdin);
    freopen("maxflowa.out","w",stdout);
    scanf("%d",&n);
    tot = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            int z;
            scanf("%d",&z);
            if(z > 0)add_(i,j,z);
        }
    }
    while(bfs()){
        update();
    }
    printf("%d\n",maxflow);
    
    return 0;
    
}