Solution UVA: 820 - Internet Bandwidth

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss820 - Internet Bandwidth	Accepted	C++11	0.000	0.000	1678	1 days ago

Suggest:

- The problem is max flow basic (i found clean code to solve)  

#include <bits/stdc++.h>

 

using namespace std;

 

const int INF = 1e9;

 

struct Edge {

    int u, v;

    int capacity;

    int flow;

};

 

struct Network {

    int n;

    int source, sink;

 

    vector<vector<int> > a;

    vector<Edge> E;

 

    vector<int> cur;

    vector<int> dist;

 

    Network() {}

    Network(int n, int s, int t) {

        this->n = n;

        source = s; sink = t;

        a = vector<vector<int> > (n + 1);

        cur = dist = vector<int> (n + 1);

    }

 

    void addEdge(int u, int v, int c) {

        a[u].push_back(E.size()); E.push_back({u, v, c, 0});

        a[v].push_back(E.size()); E.push_back({v, u, 0, 0});

    }

 

    bool bfs() {

        fill(dist.begin(), dist.end(), -1);

        queue<int> Q; Q.push(source); dist[source] = 0;

        while (!Q.empty()) {

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

            for (int i = 0; i < a[u].size(); ++i) {

                int id = a[u][i], v = E[id].v;

                if (dist[v] < 0 && E[id].flow < E[id].capacity) {

                    dist[v] =  dist[u] + 1;

                    Q.push(v);

                }

            }

        }

        return dist[sink] >= 0;

    }

 

    int dfs(int u, int flow) {

        if (!flow) return 0;

        if (u == sink) return flow;

        for (; cur[u] < a[u].size(); ++cur[u]) {

            int id = a[u][cur[u]], v = E[id].v;

            if (dist[v] != dist[u] + 1) continue;

            int delta = dfs(v, min(flow, E[id].capacity - E[id].flow));

            if (delta) {

                E[id].flow += delta; E[id ^ 1].flow -= delta;

                return delta;

            }

        }

        return 0;

    }

 

    int maxFlow() {

        int ans = 0;

        while (bfs()) {

            fill(cur.begin(), cur.end(), 0);

            while (true) {

                int delta = dfs(source, INF);

                if (!delta) break;

                ans += delta;

            }

        }

        return ans;

    }

};

 

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int n, m, s, t, cnt= 0;

    while(cin >> n && n){

       

        cin >> s >> t >> m;

        Network G (n, s, t);

        while (m--) {

            int u, v, c;

            cin >> u >> v >> c;

            G.addEdge(u, v, c);

            G.addEdge(v, u, c);

         }

        cout << "Network "<<++cnt<<"\n";

        cout <<"The bandwidth is "<<G.maxFlow()<<"."<<"\n\n";

    }

}