poj1273--Drainage Ditches（最大流Edmond-Karp算法 邻接表实现）

最大流模板题

大部分Edmond-Karp算法代码都是邻接矩阵实现，试着改成了邻接表。

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

// 裸最大流

const int N = 2005;

const int M = 2005;

const int INF = 0x7fffffff;

// 邻接表

struct Edge {

    int from, to, next, cost;

} edge[M];

int head[N];

int cnt_edge;

void add_edge(int u, int v, int c)

{

    edge[cnt_edge].to = v;

    edge[cnt_edge].from = u;

    edge[cnt_edge].cost = c;

    edge[cnt_edge].next = head[u];

    head[u] = cnt_edge++;

}

int pre[N];

int flow[N];

queue<int> q;

int bfs(int src, int des)

{

    memset(pre, -1, sizeof pre);

    while (!q.empty()) q.pop();

    q.push(src);

    flow[src] = INF;

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        if (u == des) break;

        for (int i = head[u]; i != -1; i = edge[i].next)

        {

            int v = edge[i].to;

            int cost = edge[i].cost;

            if (pre[v] == -1 && cost > 0)

            {

                flow[v] = min(flow[u], cost);

                pre[v] = i; // 记录的是边

                q.push(v);

            }

        }

    }

    if (pre[des] == -1) return -1;

    return flow[des];

}

int maxFlow(int src, int des)

{

    int ans = 0;

    int in;

    while ((in = bfs(src, des)) != -1)

    {

        int k = des;

        while (k != src)

        {

            int last = pre[k];

            edge[last].cost -= in;

            edge[last ^ 1].cost += in;

            k = edge[last].from;

        }

        ans += in;

    }

    return ans;

}

int main()

{

    int n, m;

    while (~scanf("%d%d", &m, &n))

    {

        int a, b, c;

        memset(head, -1, sizeof head);

        while (m--)

        {

            scanf("%d%d%d", &a, &b, &c);

            add_edge(a, b, c);

            add_edge(b, a, 0);

        }

        printf("%d\n", maxFlow(1, n));

    }

}

　　

另附邻接矩阵版

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#define pk puts("kk");

using namespace std;

// 裸最大流

const int N = 205;

const int INF = 0x7fffffff;

int cap[N][N];

int flow[N];

int pre[N];

queue<int> q;

int n, m;

int bfs(int src, int des)

{

    while (!q.empty()) q.pop();

    memset(pre, -1, sizeof pre);

    q.push(src);

    flow[src] = INF;

    while (!q.empty())

    {

        int idx = q.front();

        if (idx == des) break;

        q.pop();

        for (int i = 1; i <= n; ++i)

        {

            if (pre[i] == -1 && cap[idx][i] > 0)

            {

                flow[i] = min(flow[idx], cap[idx][i]);

                pre[i] = idx;

                q.push(i);

            }

        }

    }

    if (pre[des] == -1) return -1;

    return flow[des];

}

int maxFlow(int src, int des)

{

    int ans = 0;

    int in;

    while ((in = bfs(src, des)) != -1)

    {

        int k = des;

        while (k != src)

        {

            int last = pre[k];

            cap[last][k] -= in;

            cap[k][last] += in;

            k = last;

        }

        ans += in;

    }

    return ans;

}

int main()

{

    while (~scanf("%d%d", &m, &n))

    {

        int a, b, c;

        memset(cap, 0, sizeof cap);

        for (int i = 0; i < m; ++i)

        {

            scanf("%d%d%d", &a, &b, &c);

            cap[a][b] += c;

        }

        printf("%d\n", maxFlow(1, n));

    }

    return 0;

}