HDoj 3549 Flow Problem(最大ネットワークストリーム)

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3549
構想分析:この問題は裸の最大ネットワークストリーム問題で、データ量は大きくなく、EdmondsKarpアルゴリズムを使って解くことができる.この問題の点は最大15個、エッジの数は最大1000個であるため、この図には重エッジが存在し、複数の重エッジを1つのエッジに結合する必要がある.
 
コードは以下の通りです

#include <queue>
#include <vector>
#include <cstdio>
#include <climits>
#include <cstring>
#include <iostream>
using namespace std;

const int MAX_N = 20;
int cap[MAX_N][MAX_N], flow[MAX_N][MAX_N];
int a[MAX_N], p[MAX_N];

inline int Min(int a, int b) { return a < b ? a : b; }
int EdmondsKarp(int ver_num)
{
    queue<int> q;
    int max_flow = 0;

    memset(flow, 0, sizeof(flow));
    for (;;)
    {
        memset(a, 0, sizeof(a));
        a[1] = INT_MAX;
        q.push(1);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int v = 1; v <= ver_num; ++v)
            {
                if (!a[v] && cap[u][v] > flow[u][v])
                {
                    p[v] = u;
                    q.push(v);
                    a[v] = Min(a[u], cap[u][v] - flow[u][v]);
                }
            }
        }
        if (a[ver_num] == 0)  break;
        for (int u = ver_num; u != 1; u = p[u])
        {
            flow[p[u]][u] += a[ver_num];
            flow[u][p[u]] -= a[ver_num];
        }
        max_flow += a[ver_num];
    }
    return max_flow;
}


int main()
{
    int case_times, case_id = 0;
    int road_num, ver_num;

    scanf("%d", &case_times);
    while (case_times--)
    {
        int ver_1, ver_2, capa;

        scanf("%d %d", &ver_num, &road_num);
        memset(cap, 0, sizeof(cap));
        for (int i = 0; i < road_num; ++i)
        {
            scanf("%d %d %d", &ver_1, &ver_2, &capa);
            cap[ver_1][ver_2] += capa;
        }
        int ans = EdmondsKarp(ver_num);
        printf("Case %d: %d
", ++case_id, ans);
    }
    return 0;
}