记录编号	395947	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2017-04-17 17:15:23	内存使用	1.58 MiB

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

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;
}

class edge{
public:
    int fr, to, ne, v, w, vbk;// w是费用，v是流量
    edge() {;}
    inline edge(int fr_, int to_, int ne_, int v_, int w_) {
        fr = fr_, to = to_, ne = ne_, v = v_, w = w_;
        vbk = v_;
    }
}e[MAXN *(3 + MAXN)];

int cnt, head[MAXN * 3];

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

int n, m, a[MAXN], b[MAXN], s, t;
bool inq[MAXN];
int dis[MAXN], pth[MAXN];

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

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

int main() {
/*#ifdef DEBUG*/
    //freopen("in.txt", "r", stdin);
/*#endif*/
    freopen("tran.in", "r", stdin);
    freopen("tran.out", "w", stdout);
    memset(head, -1, sizeof(head));
    m = get_num();
    n = get_num();
    s = 0; 
    t = n + m + 1;
    for(int i = 1; i <= m; i++) {
        a[i] = get_num();
        addedge(s, i, 0, a[i]);

    }
    for(int i = 1; i <= n; i++) {
        b[i] = get_num();
        addedge(i + m, t, 0, b[i]);
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            addedge(i, m + j, get_num(), inf);
        }
    }
    int ans = 0;
    while(bfs()) {
        ans += get_flow() * dis[t];
    }
    printf("%d\n", ans);

    for(int i = 0; i < cnt; i++) {
        e[i].v = e[i].vbk;
        e[i].w = -1 * e[i].w;
    }

    ans = 0;
    while(bfs()) {
        ans += get_flow() * dis[t];
    }
    printf("%d", -1 * ans);

}