记录编号	395177	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-04-15 10:23:29	内存使用	1.35 MiB

#include <bits/stdc++.h>
#define MAXN 233
#define inf 0x7fffffff
using namespace std;

inline void File() {
    ////freopen("in.txt", "r", stdin);
    freopen("maxflowd.in", "r", stdin);
    freopen("maxflowd.out", "w", stdout);
}

inline int get_num() {
    int k = 0;
    char c = getchar();
    for(; !isdigit(c); c = getchar());
    for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k;
}

struct edge{
    int fr, ne, to, v, w;
    edge() {;}
    inline edge(int fr_, int ne_, int to_, int v_, int w_) {
        fr = fr_, ne = ne_, to = to_, v = v_, w = w_;
    } 
}e[MAXN * MAXN];

int head[233], cnt;

inline void addedge(int fr, int to, int v, int w) {
    e[cnt++] = edge(fr, head[fr], to, v, w), head[fr] = cnt - 1;
    e[cnt++] = edge(to, head[to], fr, 0, -w), head[to] = cnt - 1;
} 

int dis[MAXN], pre[MAXN];
int n, s, t;
bool vis[MAXN];

inline bool bfs() {
    memset(dis, 0x7f, sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis[s] = 0;
    vis[s] = 1;
    queue<int> que;
    que.push(s);
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        vis[x] = 0;
        for(int i = head[x]; ~i; i = e[i].ne) {
            int y = e[i].to;
            int z = e[i].w;
            if(!e[i].v || dis[y] <= dis[x] + z) continue;
            dis[y] = dis[x] + z;
            pre[y] = i;
            if(vis[y]) continue;
            que.push(y);
            vis[y] = 1;
        }
    }
    return ~pre[t];
}

inline int get_minflow() {
    int now = pre[t];
    int minflow = inf;
    while(~now) {
        minflow = min(minflow, e[now].v);
        now = pre[e[now].fr];
    }
    now = pre[t];
    while(~now) {
        e[now].v -= minflow;
        e[now ^ 1].v += minflow;
        now = pre[e[now].fr];
    }
    return minflow;
}



int main() {
    File();
    n = get_num();
    s = get_num();
    t = get_num();
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int x = get_num();
            int y = get_num();
            if(!x || !y) continue;
            addedge(i, j, x, y);
        }
    }
    int ans = 0;
    while(bfs()) {
        ans += get_minflow() * dis[t];
    }
    
    printf("%d", ans); 
}