HDU3549 Flow Problem（最大流模板题）

Flow Problem

Time Limit: 5000/5000 MS (Java/Others)
Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 20685
Accepted Submission(s): 9706

Problem Description

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

Input

The first line of input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

Output

For each test cases, you should output the maximum flow from source 1 to sink N.

Sample Input

Sample Output

Case 1: 1
Case 2: 2

Source

HyperHexagon's Summer Gift (Original tasks)

链接

http://acm.hdu.edu.cn/showproblem.php?pid=3549

题意&题解

最大流模板题，为了测试一下板子。

代码

Dinic

Status	Accepted
Time	109ms
Memory	1928kB
Length	2148

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;

int n, m;
struct Edge
{
    int u, v, cap;
    Edge() {}
    Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
}edge[maxn*maxn];

int R, S, T;
vector <int> E[maxn]; //边集
int dis[maxn];
int current[maxn];

void addedge(int u, int v, int cap)
{
    E[u].push_back(R);
    edge[R++] = Edge(u, v, cap); // 正向边
    E[v].push_back(R);
    edge[R++] = Edge(v, u, 0); // 方向边容量为0
    // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2，R从0开始
}

int bfs()
{
    memset(dis, 0x3f, sizeof(dis)); // 初始化为0x3f3f3f3f
    queue <int> Q;
    Q.push(S);
    dis[S] = 0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < E[u].size(); ++i)
        {
            Edge &e = edge[E[u][i]];
            if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
            {
                dis[e.v] = dis[u] + 1;
                Q.push(e.v);
            }
        }
    }
    return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}

int dinic(int u, int maxflow)
{
    if (u == T)
        return maxflow;
    for (int i = current[u]; i < E[u].size(); ++i) // 当前弧优化，保存u点增广到了第几条边
    {
        current[u] = i;
        Edge &e = edge[E[u][i]];
        if (dis[e.v] == dis[u] + 1 && e.cap > 0)
        {
            int flow = dinic(e.v, min(maxflow, e.cap));
            if (flow)
            {
                e.cap -= flow; // 正向边流量减少
                edge[E[u][i] ^ 1].cap += flow; // 方向边流量增加
                return flow;
            }
        }
    }
    return 0;
}

int DINIC()
{
    int ans = 0;
    while (bfs())
    {
        int flow;
        memset(current, 0, sizeof(current)); // bfs后清空当前弧数组
        while (flow = dinic(S, 0x3f3f3f3f)) // 一次bfs可以进行多次增广
            ans += flow;
    }
    return ans;
}

int main()
{
    int t, u, v, cap, kase = 0;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        R = 0, S = 1, T = n; // 边序号，源点，汇点
        for (int i = 0; i <= n; ++i)
            E[i].clear();
        memset(edge, 0, sizeof(edge));
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &cap);
            addedge(u, v, cap);
        }
        printf("Case %d: %d\n", ++kase, DINIC());
    }
    return 0;
}

EK邻接表

tatus	Accepted
Time	1560ms
Memory	13728kB
Length	1921

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

struct Edge
{
    int next, to, w;
}edge[maxn*maxn];
struct Node
{
    int id, v;
}pre[maxn];
int head[maxn];
int n, m, cnt;
bool vis[maxn];

void init()
{
    cnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

bool bfs(int s, int t)
{
    memset(pre, -1, sizeof(pre));
    memset(vis, 0, sizeof(vis));
    queue <int> Q;
    Q.push(s);
    vis[s] = true;
    pre[s].v = s;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if (!vis[v] && edge[i].w > 0)
            {
                pre[v].v = u;
                pre[v].id = i;
                vis[v] = true;
                if (v == t)
                    return true;
                Q.push(v);
            }
        }
    }
    return false;
}

int EK(int s, int t)
{
    int maxflow = 0;
    while (bfs(s, t))
    {
        int _min = inf;
        for (int i = t; i != s; i = pre[i].v)
            _min = min(_min, edge[pre[i].id].w);
        for (int i = t; i != s; i = pre[i].v)
        {
            edge[pre[i].id].w -= _min;
            edge[pre[i].id ^ 1].w += _min;
        }
        maxflow += _min;
    }
    return maxflow;
}

int main()
{
    int T, u, v, w, kase = 0;
    scanf("%d", &T);
    while (T--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, 0);
        }
        printf("Case %d: %d\n", ++kase, EK(1, n));
    }
    return 0;
}

EK邻接矩阵

Status	Accepted
Time	546ms
Memory	5748kB
Length	1487

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int G[maxn][maxn];
int n, m;
bool vis[maxn];
int pre[maxn];

bool bfs(int s, int t)
{
    queue <int> Q;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    Q.push(s);
    vis[s] = true;
    pre[s] = s;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if (G[u][i] > 0 && !vis[i])
            {
                pre[i] = u;
                vis[i] = true;
                if (i == t)
                    return true;
                Q.push(i);
            }
        }
    }
    return false;
}

int EK(int s, int t)
{
    int maxflow = 0;
    while (bfs(s, t)) // 寻找增广路
    {
        int _min = inf;
        for (int i = t; i != s; i = pre[i])
            _min = min(_min, G[pre[i]][i]);
        for (int i = t; i != s; i = pre[i])
        {
            G[pre[i]][i] -= _min;
            G[i][pre[i]] += _min;
        }
        maxflow += _min;
    }
    return maxflow;
}

int main()
{
    int T, u, v, w, kase = 0;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        memset(G, 0, sizeof(G));
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            G[u][v] += w;
        }
        printf("Case %d: %d\n", ++kase, EK(1, n));
    }
    return 0;
}

可以看出来时间效率还是差了挺多的。