UVA 820 Internet Bandwidth

UVA 820 Internet Bandwidth

題意：
基本的 max-flow 問題，使用Edmonds–Karp algorithm 實作 Ford–Fulkerson method，時間複雜度：O(V E2)

測資：

4 1 4 5 (1=start,4=terminate,5=connection) 1 2 20 1 3 10 2 3 5 2 4 10 3 4 20 0

Network 1 The bandwidth is 25.

程式碼：

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<queue>

using namespace std;

int map[105][105]= {0};

queue<int> q;

int pre[105]={0};

bool bfs(int s,int t,int n) //尋找從起點到終點的一條路徑

{

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

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

    pre[s]=0;

    q.push(s);

    while(!q.empty())

    {

        int ind=q.front();

        q.pop();

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

        {

            if(pre[i]==-1&&map[ind][i]>0) //尚未走過且流量>0

            {

                pre[i]=ind;

                if(i==t) return true;

                q.push(i);

            }

        }

    }

    return false;

}

int ek(int s,int t,int n)

{

    int maxflow=0;

    while(bfs(s,t,n)) //直到不能再從起點走到終點

    {

        int minflow=1e7; //將初始流量設最大

        int i;

        for(int i=t; i!=s; i=pre[i])

        {

            minflow=min(minflow,map[pre[i]][i]); //路徑上最小容量(=這次可流通的最大流量)

        }

        for(int i=t; i!=s; i=pre[i])

        {

            map[pre[i]][i]-=minflow; //正向減流

            map[i][pre[i]]+=minflow; //反向加流

        }

        maxflow+=minflow; 

    }

    return maxflow;

}

int main()

{

    int n;

    int test=1;

    while(cin>>n&&n!=0)

    {

        memset(map,0,sizeof(map));

        int s,t,c;

        cin>>s>>t>>c;

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

        {

            int a,b,w;

            cin>>a>>b>>w;

            map[a][b]+=w;

            map[b][a]+=w;

        }

        cout<<"Network "<<test<<endl<<"The bandwidth is "<<ek(s,t,n)<<'.'<<endl;

        test++;

        cout<<endl;

    }

    return 0;

}