Algorithms/Max_Flow.cpp at master · asimali246/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <vector>
#include <new>
#include <bitset>
#include <ctime>

 using namespace std;

#define ll long long int
#define INF 1000000000
#define PI acos(-1.0)
#define EPS 1e-9

template <typename X> X gcd(X a, X b){if(!b)return a; else return gcd(b, a%b);}

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, ll> llp;
typedef pair<double, double> dd;
typedef pair<char, int> ci;

int n, s, t, c, cs=1, mf, f, x, y, cost, i, j;
vector<vector<ii> > adj;
int res[111][111];
vi p;
bitset<111> bs;
queue<int> q;

void augment(int v, int minCost)
{
    if(v==s)
    {
        f=minCost;
        return;
    }
    else
    if(p[v]!=-1)
    {
        augment(p[v], min(minCost, res[p[v]][v]));
        res[p[v]][v]-=f;
        res[v][p[v]]+=f;
    }
}

int main()
{
    adj.clear(), p.clear();
    adj.assign(111, vector<ii>());
    p.assign(111, -1);
    while(1)
    {
        scanf("%d", &n);
        if(!n)
            break;
        mf=0;
        scanf("%d %d %d", &s, &t, &c);
        for(i=1;i<=n;++i)
            adj[i].clear();
        memset(res, 0, sizeof res);
        while(c--)
        {
            scanf("%d %d %d", &x, &y, &cost);
            adj[x].push_back(ii(y, cost));
            adj[y].push_back(ii(x, cost));
            res[x][y]+=cost;
            res[y][x]+=cost;
        }
        while(1)
        {
            for(i=1;i<=n;++i)
                p[i]=-1;
            q=queue<int>();
            bs.reset();
            q.push(s);
            bs[s]=1;
            f=0;
            while(!q.empty())
            {
                int u=q.front();q.pop();
                if(u==t)
                    break;
                for(j=0;j<(int)adj[u].size();++j)
                {
                    ii v=adj[u][j];
                    if(res[u][v.first]>0 && !bs[v.first])
                    {
                        bs[v.first]=1;
                        p[v.first]=u;
                        q.push(v.first);
                    }
                }
            }
            augment(t, INF);
            if(f==0)
                break;
            mf+=f;
        }
        printf("Network %d\n", cs++);
        printf("The bandwidth is %d.\n", mf);
        putchar('\n');
    }
    return 0;
}