Cod sursa(job #2115958)

Utilizator LucaSeriSeritan Luca LucaSeri Data 27 ianuarie 2018 11:31:59
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 105;

vector< int > gr[MaxN];

int capacity[MaxN][MaxN];
int current_flow[MaxN][MaxN];
int boss[MaxN];
bool viz[MaxN];

bool can_push(int source, int target){
    memset(boss, 0, sizeof boss);
    memset(viz, 0, sizeof viz);

    queue< int > q;
    q.push(source);

    while(q.size()){
        int node = q.front();
        q.pop();
        if(node == target) continue;
        for(auto x : gr[node]){
            if(viz[x] == 0 && current_flow[node][x] < capacity[node][x]){
                boss[x] = node;
                viz[x] = true;
                q.push(x);
            }
        }

    }


    return viz[target];

}

void update_flow(int source, int target, int & ans){
    for(auto x : gr[target]){
        if(boss[x] == 0) continue;
        boss[target] = x;
        int node = target;
        int minimum_flow = 1<<30;
        while(node != source){
            minimum_flow = min(minimum_flow, capacity[ boss[node] ][node] - current_flow[ boss[node] ][node]);
            node = boss[node];
        }

        node = target;

        while(node != source){
            current_flow[ boss[node] ][node] += minimum_flow;
            current_flow[node][ boss[node] ] -= minimum_flow;
            node = boss[node];
        }

        ans += minimum_flow;
    }
}
int main(){

    ifstream f("harta.in");
    ofstream g("harta.out");

    int n;
    f >> n;

    int source = 0;
    int target = n<<1|1;

    for(int i = 1; i <= n; ++i){
        int x, y;
        f >> x >> y;

        gr[source].push_back(i);
        gr[i].push_back(source);
        capacity[source][i] = x;

        gr[target].push_back(n + i);
        gr[n + i].push_back(target);
        capacity[n + i][target] = y;


        for(int j = 1; j <= n; ++j){
            if(i == j) continue;
            gr[i].push_back(j + n);
            gr[j + n].push_back(i);
            capacity[i][j + n] = 1;
        }
    }

    int max_flow = 0;

    while(can_push(source, target)) update_flow(source, target, max_flow);

    g << max_flow << '\n';
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(current_flow[i][j + n]) g << i << ' ' << j << '\n';
        }
    }
    return 0;
}