MENU

HDU3549 Flow Problem(最大流模板题)

2018 年 07 月 22 日 • 阅读: 1423 • 图论阅读设置

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

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1 

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
StatusAccepted
Time109ms
Memory1928kB
Length2148
#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邻接表
tatusAccepted
Time1560ms
Memory13728kB
Length1921
#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邻接矩阵
StatusAccepted
Time546ms
Memory5748kB
Length1487
#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;
}

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


推荐


The end.
2018-07-22 星期日