记录编号	555047	评测结果	AAAAAAAAAA
题目名称	11.运输问题1	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-09-26 07:06:22	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 110;

struct EDGE{
    int to;
    EDGE *next;
    int v;
};

void addEdge(int from, int to, int flow, EDGE *head[]);
bool bfs(int S);
int dfs(int now, int minflow);

int N, S, T;
EDGE *head[MAXN];
int deep[MAXN];

int main() {
#ifndef LOCAL
    freopen("maxflowa.in", "r", stdin);
    freopen("maxflowa.out", "w", stdout);
#endif
    scanf("%d", &N);
    S = 0, T = N - 1;
    for(int i = 0, j, k; i < N; ++i) {
        for(j = 0; j < N; ++j) {
            scanf("%d", &k);
            if(k > 0) addEdge(i, j, k, head);
        }
    }
    int ans = 0;
    while(bfs(S)) {
        ans += dfs(S, INT_MAX);
    }
    printf("%d\n", ans);
    return 0;
}

void addEdge(int from, int to, int flow, EDGE *head[]) {
    head[from] = new (EDGE){to, head[from], flow};
}

bool bfs(int S) {
    static queue<int> que;
    while(!que.empty()) que.pop();
    memset(deep, 0x00, sizeof(deep));
    deep[S] = 1;
    que.push(S);
    while(!que.empty()) {
        int from = que.front();
        que.pop();
        for(EDGE *e = head[from]; e; e = e->next) {
            if(deep[e->to] || e->v <= 0) continue;
            deep[e->to] = deep[from] + 1;
            if(e->to == T) return true;
            que.push(e->to);
        }
    }
    return false;
}

int dfs(int now, int minflow) {
    if(now == T) return minflow;
    int nowflow;
    for(EDGE *e = head[now]; e; e = e->next) {
        if(deep[now] + 1 != deep[e->to]) continue;
        nowflow = dfs(e->to, min(minflow, e->v));
        if(!nowflow) continue;
        e->v -= nowflow;
        return nowflow;
    }
    return 0;
}