网络流 HDU 3549 Flow Problem

题目：

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

用增广路算法进行求解。注意的问题有两个：

1. 每次增广的时候，反向流量也要进行更行。一開始没注意，WA了几次 ORZ

2. 对于输入的数据，容量要进行累加更新。

// 邻接矩阵存储

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x7fffffff;

const int M = 15+5;

int c[M][M];    // capacity

int f[M][M];    // flow

int flow[M];    // current flows

int p[M];       // path

// 增广路算法

long long MaxFlow(int n)

{

    long long cnt = 0;

    while(true)

    {

        queue<int> q;

        q.push(1);

        memset(flow, 0, sizeof(flow));

        flow[1] = INF;

        while(!q.empty())

        {

            int u = q.front();

            q.pop();

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

            {

                if ( u != v && c[u][v] > f[u][v] && !flow[v] /*避免回环*/ )

                {

                    q.push(v);

                    flow[v] = min(flow[u], c[u][v]-f[u][v]);

                    p[v] = u;

                }

            }

        }

        if (flow[n]==0)

            break;  // 无增广了, 退出

        // 进行增广

        //cout<<flow[n]<<endl;

        for(int v=n; v != 1; v=p[v])

        {

            f[p[v]][v] += flow[n];

            f[v][p[v]] -= flow[n];  // 反向更新, 有流入。流出自然也应该添加！

WA 了几次才发现 orz

        }

        cnt += flow[n];

    }

    return cnt;

}

int main(void)

{

    //freopen("in.txt", "r", stdin);

    int iCase =1;

    int t = 0;

    cin>>t;

    while(t--)

    {

        memset(c, 0, sizeof(c));

        memset(f, 0, sizeof(f));

        int n, m;

        scanf("%d%d", &n, &m);

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

        {

            int s,e,v;

            scanf("%d%d%d", &s, &e, &v);

            c[s][e] += v;       // 流入的容量要进行累加

        }

        // 特例直接推断

        if (n <= 1 || m < 1)

        {

            printf("Case %d: 0\n", iCase++);

            continue;

        }

        long long cnt = MaxFlow(n);

        printf("Case %d: %lld\n", iCase++, cnt);

    }

    return 0;

}