Cod sursa(job #1722121)

Utilizator cristina_borzaCristina Borza cristina_borza Data 27 iunie 2016 13:26:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

int t[1005] , c[1005][1005] , flow[1005][1005];
int n , m , cost , flux , node1 , node2;

vector <vector <int> > G;

bool bfs();

int main() {
    f >> n;
    G.resize(2 * n + 5);

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

        G[1].push_back(i + 1);
        G[i + 1].push_back(1);

        c[n + i + 1][2 * n + 2] = y;

        G[n + i + 1].push_back(2 * n + 2);
        G[2 * n + 2].push_back(n + i + 1);
    }

    for (int i = 2; i <= n + 1; ++i) {
        for (int j = n + 2; j <= 2 * n + 1; ++j) {
            if (i - 1 == j - n - 1) {
                continue;
            }
            c[i][j] = 1;
            G[i].push_back(j);
            G[j].push_back(i);
        }
    }

     while(bfs()) {
        for(vector <int>::iterator it = G[2 * n + 2].begin() ; it != G[2 * n + 2].end() ; ++it) {
            if(flow[*it][2 * n + 2] < c[*it][2 * n + 2] && t[*it]) {
                int u = *it , val = c[*it][2 * n + 2] - flow[*it][2 * n + 2];
                while(u != 1) {
                    val = min(val , c[t[u]][u] - flow[t[u]][u]);
                    u = t[u];
                }

                u = *it;
                flow[*it][2 * n + 2] += val;
                flow[2 * n + 2][*it] -= val;

                while(u != 1)
                {
                    flow[t[u]][u] += val;
                    flow[u][t[u]] -= val;
                    u = t[u];
                }
                flux += val;
            }
        }
    }

    g << flux << '\n';
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = n + 2; j <= 2 * n + 1; ++j) {
            if (i - 1 == j - n - 1) {
                continue;
            }

            if (flow[i][j] == 1) {
                g << i - 1 << " " << j - n - 1 << '\n';
            }
        }
    }
    return 0;
}

bool bfs() {
    queue <int> q;
    q.push(1);

    memset(t , 0 , sizeof(t));
    t[1] = -1;

    while(!q.empty()) {
        int node = q.front();
        for(vector <int> :: iterator  it = G[node].begin() ; it != G[node].end() ; ++it) {
            if(flow[node][*it] < c[node][*it] && !t[*it]) {
                q.push(*it);
                t[*it] = node;
            }
        }
        q.pop();
    }

    return (t[n] != 0);
}