Cod sursa(job #1462589)

Utilizator jul123Iulia Duta jul123 Data 18 iulie 2015 16:16:30
Problema Flux maxim Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<bits/stdc++.h>

using namespace std;

int n;
queue<int> q;
int flux[1001][1001], cap[1001][1001], tata[1005];
bool viz[1005];
vector<int> v[1005];

int bfs() {
    memset(viz, 0, sizeof(viz));
    q.push(0);
    viz[0] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x != n) {
            for(int i = 0; i < v[x].size(); ++i) {
                if(viz[v[x][i]] == 0 && flux[x][v[x][i]] != cap[x][v[x][i]]) {
                    viz[v[x][i]] = 1;
                    q.push(v[x][i]);
                    tata[v[x][i]] = x;
                }

            }
        }
    }
    return viz[n - 1];
}

int main()
{
    int m, a, b, c;
    FILE *fin = fopen("maxflow.in", "r");
    FILE *fout = fopen("maxflow.out", "w");

    fscanf(fin, "%d %d", &n, &m);

    for(int i = 0; i < m; ++i) {
        fscanf(fin, "%d %d %d", &a, &b, &c);
        --a; --b;
        v[a].push_back(b);
        v[b].push_back(a);
        cap[a][b] = c;
    }

    int flow = 0;
    bool ok = bfs();
    while(ok) {
        for(int i = 0; i < v[n - 1].size(); ++i) {
            if(viz[v[n - 1][i]] == 1 && flux[v[n - 1][i]][n - 1] != cap[v[n - 1][i]][n - 1]) {
                tata[n - 1] = v[n - 1][i];
                int minim = 200000;
                for(int j = n - 1; j != 0 ; j = tata[j]) {
                    if(minim > cap[tata[j]][j] - flux[tata[j]][j])
                        minim = cap[tata[j]][j] - flux[tata[j]][j];
                }
                if(minim != 0) {
                    for(int j = n - 1; j != 0 ; j = tata[j]) {
                        flux[tata[j]][j] += minim;
                        flux[j][tata[j]] -= minim;
                    }
                    flow += minim;
                }
            }
        }
        ok = bfs();
    }
    fprintf(fout, "%d", flow);
}