2013-team5/andrew/13/A

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 200;
const int MAXM = 100000;
const int inf = 1e9;

struct Node {
    int u, v, f, c;
    int next;
};

bool vis[MAXN];
int dis[MAXN], pre[MAXN], head[MAXN];
Node e[MAXM];
int N, M, cnt, S, T;

inline void addedge(int u, int v, int f, int c) {
    e[cnt].u = u; e[cnt].v = v; e[cnt].c = c; e[cnt].f = f;
    e[cnt].next = head[u]; head[u] = cnt ++;
    e[cnt].u = v; e[cnt].v = u; e[cnt].c = -c; e[cnt].f = 0;
    e[cnt].next = head[v]; head[v] = cnt ++;
}

bool spfa() {
    queue<int> Q;
    while (!Q.empty()) Q.pop();
    for (int i = 0; i <= T; ++ i) {
        dis[i] = inf;
        vis[i] = 0;
        pre[i] = -1;
    }
    Q.push(S); vis[S] = 1; dis[S] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int now = head[u]; now != -1; now = e[now].next) {
            int v = e[now].v;
            if (e[now].f > 0 && dis[v] > dis[u] + e[now].c) {
                dis[v] = dis[u] + e[now].c;
                pre[v] = now;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
        vis[u] = false;
    }
    return dis[T] < inf;
}

int MCMF() {
    int mincost = 0, maxflow = 0;
    while (spfa()) {
        int nec = inf;
        for (int now = pre[T]; now != -1; now = pre[e[now].u])
            nec = min(nec, e[now].f);
        mincost += nec * dis[T];
        maxflow += nec;
        for (int now = pre[T]; now != -1; now = pre[e[now].u]) {
            e[now].f -= nec;
            e[now ^ 1].f += nec;
        }
    }
    return mincost;
}

int main() {
    freopen("assignment.in", "r", stdin);
    freopen("assignment.out", "w", stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    S = 0; T = 2 * n + 1; cnt = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            int x; scanf("%d", &x);
            addedge(i, j + n, 1, x);
        }
    }
    for (int i = 1; i <= n; ++ i) addedge(S, i, k, 0);
    for (int j = 1; j <= n; ++ j) addedge(j + n, T, k, 0);
    int ret = MCMF();
    printf("%d\n", ret);
    fclose(stdin); fclose(stdout);
    return 0;
}
}}}

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 200;
const int MAXM = 100000;
const int inf = 1e9;
struct Node {
    int u, v, f, c;
    int next;
};
bool vis[MAXN];
int dis[MAXN], pre[MAXN], head[MAXN];
Node e[MAXM];
int N, M, cnt, S, T;
inline void addedge(int u, int v, int f, int c) {
    e[cnt].u = u; e[cnt].v = v; e[cnt].c = c; e[cnt].f = f;
    e[cnt].next = head[u]; head[u] = cnt ++;
    e[cnt].u = v; e[cnt].v = u; e[cnt].c = -c; e[cnt].f = 0;
    e[cnt].next = head[v]; head[v] = cnt ++;
}
bool spfa() {
    queue<int> Q;
    while (!Q.empty()) Q.pop();
    for (int i = 0; i <= T; ++ i) {
        dis[i] = inf;
        vis[i] = 0;
        pre[i] = -1;
    }
    Q.push(S); vis[S] = 1; dis[S] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int now = head[u]; now != -1; now = e[now].next) {
            int v = e[now].v;
            if (e[now].f > 0 && dis[v] > dis[u] + e[now].c) {
                dis[v] = dis[u] + e[now].c;
                pre[v] = now;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
        vis[u] = false;
    }
    return dis[T] < inf;
}
int MCMF() {
    int mincost = 0, maxflow = 0;
    while (spfa()) {
        int nec = inf;
        for (int now = pre[T]; now != -1; now = pre[e[now].u])
            nec = min(nec, e[now].f);
        mincost += nec * dis[T];
        maxflow += nec;
        for (int now = pre[T]; now != -1; now = pre[e[now].u]) {
            e[now].f -= nec;
            e[now ^ 1].f += nec;
        }
    }
    return mincost;
}
int main() {
    freopen("assignment.in", "r", stdin);
    freopen("assignment.out", "w", stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    S = 0; T = 2 * n + 1; cnt = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            int x; scanf("%d", &x);
            addedge(i, j + n, 1, x);
        }
    }
    for (int i = 1; i <= n; ++ i) addedge(S, i, k, 0);
    for (int j = 1; j <= n; ++ j) addedge(j + n, T, k, 0);
    int ret = MCMF();
    printf("%d\n", ret);
    fclose(stdin); fclose(stdout);
    return 0;
}