网络流经典模版题

Dinic……

YY 出了一个邻接表的程序然后 1A 了于是上来粘一发板子

#include <cstdio>
#include <cstring>
#include <vector>
inline int min(int a, int b) { return a < b ? a : b; }
static const int MAXN = 208;
static const int INF = 0x3fffffff;
struct edge {
    int dest, len;
    int rev_id;

    edge() { }
    edge(int v, int w) : dest(v), len(w) { }
    edge(int v, int w, int r) : dest(v), len(w), rev_id(r) { }
};
typedef std::vector<edge> edgelist;

int n, m;
edgelist e[MAXN];

int dist[MAXN];
bool dinic_level()
{
    memset(dist, -1, sizeof dist);
    static int q[MAXN], qhead, qtail;
    qhead = 1; qtail = 0; q[0] = 0; dist[0] = 0;
    while (qhead != qtail) {
        int r = q[qtail++];
        for (edgelist::iterator i = e[r].begin(); i != e[r].end(); ++i)
            if (i->len > 0 && dist[i->dest] == -1) {
                dist[i->dest] = dist[r] + 1;
                q[qhead++] = i->dest;
            }
    }
    return (dist[n - 1] > 0);
}

int dinic_augment(int u, int cap = INF)
{
    if (u == n - 1) return cap;
    int cur;
    for (edgelist::iterator i = e[u].begin(); i != e[u].end(); ++i)
        if (dist[i->dest] == dist[u] + 1 && (cur = dinic_augment(i->dest, min(cap, i->len))) > 0) {
            i->len -= cur;
            e[i->dest][i->rev_id].len += cur;
            return cur;
        }
    return 0;
}

int dinic()
{
    int ans = 0, aug;
    while (dinic_level())
        while ((aug = dinic_augment(0)) > 0) ans += aug;
    return ans;
}

bool work()
{
    if (scanf("%d%d", &m, &n) != 2) return false;

    for (int i = 0; i < n; ++i) e[i].clear();
    int u, v, w;
    while (m--) {
        scanf("%d%d%d", &u, &v, &w); --u; --v;
        e[u].push_back(edge(v, w, e[v].size()));
        e[v].push_back(edge(u, 0, e[u].size() - 1));
    }
    printf("%d\n", dinic());

    return true;
}

int main()
{
    while (work());
    return 0;
}

以及正常的邻接矩阵……

#include <stdio.h>
#include <string.h>
#define MAXN 205
#define INF 0x3fffffff
int min(int a, int b) { return a < b ? a : b; }

int n, m;
int a[MAXN][MAXN];

int dist[MAXN];
unsigned char dinic_level()
{
    memset(dist, -1, sizeof dist);
    static int q[MAXN];
    int qhead = 1, qtail = 0, i, r;
    q[0] = 0; dist[0] = 0;
    while (qtail < qhead) {
        r = q[qtail++];
        for (i = 0; i < n; ++i) if (dist[i] == -1 && a[r][i] > 0) {
            dist[i] = dist[r] + 1;
            q[qhead++] = i;
        }
    }
    return (dist[n - 1] > 0);
}

int dinic_augment(int u, int cap)
{
    if (u == n - 1) return cap;
    int i, cur;
    for (i = 0; i < n; ++i)
        if (a[u][i] > 0 && dist[i] == dist[u] + 1
            && (cur = dinic_augment(i, min(cap, a[u][i]))) > 0)
        {
            a[u][i] -= cur;
            a[i][u] += cur;
            return cur;
        }
    return 0;
}

int dinic()
{
    int ans = 0, aug;
    while (dinic_level())
        while ((aug = dinic_augment(0, INF)) > 0) ans += aug;
    return ans;
}

unsigned char work()
{
    if (scanf("%d%d", &m, &n) != 2) return 0;
    memset(a, 0, sizeof a);
    int u, v, w;
    while (m--) {
        scanf("%d%d%d", &u, &v, &w);
        a[u - 1][v - 1] += w;
    }
    printf("%d\n", dinic());
    return 1;
}

int main()
{
    while (work());
    return 0;
}