一般的な拡張方法はネットの最大の流れを求めます(Ford-Fulkersonアルゴリズム)

/*

Time：2015-6-18

         

       ————Ford-Fulkerson  

  ：       

  ：   0    1          1 n       1

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;



const int INF = 0x7fffffff;//   

const int maxn = 1000 + 10;//           

int n, m;

int flag[maxn], pre[maxn], alpha[maxn];

int c[maxn][maxn], f[maxn][maxn];

queue<int>Q;



int main()

{

    int i, j, u, v, cc, ff;

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

    for (i = 0; i<n; i++) for (j = 0; j<n; j++) c[i][j] = INF, f[i][j] = INF; //       

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

    {

        scanf("%d%d%d%d", &u, &v, &cc, &ff);//      ，    ，    ，    

        

        //      

        if (c[u][v] == INF) { c[u][v] = cc; f[u][v] = ff; }

        else { c[u][v] += cc; f[u][v] += ff; }

    }

    //0    n-1  

    int startt, endd;

    startt = 0;

    endd = n - 1;

    while (1)

    {

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

        memset(flag, -1, sizeof(flag));

        memset(pre, -1, sizeof(pre));

        memset(alpha, -1, sizeof(alpha));

        flag[startt] = 0;//               

        pre[startt] = 0;//        

        alpha[startt] = INF;//      INF   

        Q.push(startt);

        while ((!Q.empty()) && flag[endd] == -1)

        {

            int h = Q.front(); Q.pop();

            for (i = 0; i<n; i++)

            {

                //   

                if (c[h][i] != INF)//  

                {

                    if (f[h][i]<c[h][i])//   

                    {

                        if (flag[i] == -1)//i     

                        {

                            flag[i] = 0;//i               

                            pre[i] = h;//i h   

                            //alpha[i]   alpha[h] c[h][i]-f[h][i]    

                            if (c[h][i] - f[h][i] <= alpha[h]) alpha[i] = c[h][i] - f[h][i];

                            else alpha[i] = alpha[h];

                            Q.push(i);//i               

                        }

                    }

                }

                //   

                if (c[i][h] != INF)//  

                {

                    if (f[i][h]>0)//    

                    {

                        if (flag[i] == -1)//i     

                        {

                            flag[i] = 0;//i               

                            pre[i] = -h;//i h       -       

                            //alpha[i]   alpha[h] f[i][h]    

                            if (alpha[h] <= f[i][h]) alpha[i] = alpha[h];

                            else alpha[i] = f[i][h];

                            Q.push(i);//i               

                        }

                    }

                }

            }

            flag[h] = 1;//h     ，             

        }

        if (flag[endd] == -1 || alpha[endd] == 0) break; //        ，    

        int a = alpha[endd];//    

        int now = endd;

        while (1)

        {

            if (now == 0) break;

            if (pre[now] >= 0)

            {

                f[pre[now]][now] += a;

                now = pre[now];

            }

            else if (pre[now]<0)

            {

                f[now][-pre[now]] -= a;

                now = -pre[now];

            }

        }



    }

    for (i = 0; i<n; i++)

    for (j = 0; j<n; j++)

    if (f[i][j] != INF)

        printf("%d --> %d : %d
", i, j, f[i][j]);

    int maxflow = 0;

    for (i = 0; i<n; i++) if (f[0][i] != INF)  maxflow += f[0][i];

    printf("maxflow = %d
", maxflow);

    return 0;

}