uva_820

c++

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef int Graph[100][100];  // adjacency matrix
Graph C, F, R;      // 容量上限、流量、剩餘容量
bool visit[100];     // 記錄BFS經過的點
int path[100];       // 記錄BFS tree
int bottleneck[100]; // 記錄源點到各個點的流量瓶頸
// 用法類似於最短路徑演算法的dist陣列
int Edmonds_Karp(int,int,int);
int BFS(int,int,int);



int main(int argc, const char * argv[]) {
    // insert code here...

    int n_point;
    int s;
    int t;
    int n_path;
    int first;
    int second;
    int bandwidth;
    int n_net=0;

    //memset(C, 0, sizeof(C));

    do{
        n_net++;
        memset(C, 0, sizeof(C));
        scanf("%d",&n_point);
        if(!n_point) break;
        scanf("%d %d %d",&s,&t,&n_path);
        for(int i=0;i<n_path;i++){
            scanf("%d %d %d",&first,&second,&bandwidth);
            C[first-1][second-1]+=bandwidth;
            C[second-1][first-1]+=bandwidth;
        }

        /*for(int i=0;i<n_point;i++){
            for(int j=0;j<n_point;j++){
                printf("%d ",C[i][j]);
            }
            printf("\n");
        }*/

        printf("Network %d\n",n_net);
        printf("The bandwidth is %d.\n\n",Edmonds_Karp(s-1, t-1, n_point));

        //printf("Edmonds_Karp:%d\n",Edmonds_Karp(s-1, t-1, n_point));
    }while(true);



    return 0;
}



int BFS(int s, int t,int n_point)   // 源點與匯點
{
    memset(visit, false, sizeof(visit));

    queue<int> Q;

    visit[s] = true;
    path[s] = s;
    bottleneck[s] = 1e9;
    Q.push(s);

    while (!Q.empty())
    {
        int i = Q.front(); Q.pop();
        for (int j=0; j<n_point; ++j)
            // 在剩餘容量的圖上找augmenting path
            if (!visit[j] && R[i][j] > 0 && C[i][j]>0)
            {
                visit[j] = true;
                path[j] = i;
                // 一邊找最短路徑，一邊計算流量瓶頸。
                bottleneck[j] = min(bottleneck[i], R[i][j]);
                Q.push(j);

                if (j == t){
                    //printf("bottleneck:%d\n",bottleneck[t]);
                    return bottleneck[t];
                }

            }
    }
    return 0;   // 找不到augmenting path了，流量為零。
}

int Edmonds_Karp(int s, int t,int n_point)
{

    memset(F, 0, sizeof(F));
    memcpy(R, C, sizeof(C));

    int f, df;  // 最大流的流量、擴充路徑的流量
    for (f=0; (df=BFS(s, t,n_point)); f+=df)
        // 更新擴充路徑上每一條邊的流量
        for (int i=path[t], j=t; i!=j; i=path[j=i])
        {
            F[i][j] = F[i][j] + df;
            F[j][i] = -F[i][j];
            R[i][j] = C[i][j] - F[i][j];
            R[j][i] = C[j][i] - F[j][i];
        }
    return f;
}