Cod sursa(job #2746277)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 27 aprilie 2021 17:38:49
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
#define nmax 1005
#define inf 1000000009
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");

vector<int> lista[nmax];
vector<int> adj[nmax];
int flow[nmax][nmax], capacity[nmax][nmax], level[nmax], ptr[nmax];
int n,m;
queue<int> q;

bool bfs(int start, int end){
    for(int i=0; i<=n; i++){
        level[i] = 0;
        ptr[i] = 0; 
    }
    level[start] = 1;
    q.push(start);
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        adj[nod].clear();
        for(auto neigh: lista[nod]){
            if(capacity[nod][neigh] <= flow[nod][neigh]) continue;
            if(!level[neigh]){
                level[neigh] = level[nod] + 1;
                q.push(neigh);
            }
            if(level[neigh] == level[nod] + 1){
                adj[nod].push_back(neigh);
            }
        }
    }
    return level[end];
}

int dfs(int node, int end, int flw){
    if(node == end){
        return flw;
    }
    while(ptr[node] < adj[node].size()){
        int neigh = adj[node][ptr[node]];
        if(capacity[node][neigh] > flow[node][neigh]){
            int cur_flow = min(flw, capacity[node][neigh] - flow[node][neigh]);
            int temp_flow = dfs(neigh, end, cur_flow);
            if(temp_flow > 0){
                flow[node][neigh] += temp_flow;
                flow[neigh][node] -= temp_flow;
                return temp_flow;
            }
        }
        ptr[node]++;
    }
    return 0;
}

int Dinic(int s, int t){
    if(s == t) return -1;
    int total = 0;
    while(bfs(s,t)){
        while(int fl = dfs(s,t,inf)){
            total += fl;
        }
    }
    return total;
}

int main(){
    in >> n;
    in >> m;
    for(int i=0; i<m; i++){
        int x, y;
        in >> x >> y;
        if(!capacity[x][y] && !capacity[y][x]){
            lista[x].push_back(y);
            lista[y].push_back(x);
        }
        in >> capacity[x][y];
    }
    cout << Dinic(1, n) << '\n';
    return 0;
}