Translate

Views

Tuesday, January 16, 2024

Solution UVA: 820 - Internet Bandwidth


 Problem  VerdictLangTimeBestRankSubmit Time
 | discuss820 - Internet Bandwidth AcceptedC++110.0000.00016781 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";
    }
}
 


No comments: