Cod sursa(job #1442294)

Utilizator nytr0gennytr0gen nytr0gen Data 24 mai 2015 22:43:54
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <iostream>
#include <queue>
#include <bitset>
 
using namespace std;
 
const int INF = 1<<30;
const int NMAX = 2 * 100 + 2; // 2 noduri pt fiecare oras + super source, super sink
 
vector<int> adjacent[NMAX];
int capacity[NMAX][NMAX]; // speram ca se initializeaza cu zero ^^

int findPath(const int source, const int sink) {
    queue<int> Q;
    bitset<NMAX> visited;

    Q.push(source);
    visited[source] = true;

	vector<int> from(NMAX, -1);

    int where;
    while (!Q.empty()) {
        where = Q.front(); Q.pop();
        for (int next: adjacent[where]) {
            if (!visited[next] && capacity[where][next] > 0) {
                Q.push(next);
                visited[next] = 1;
                from[next] = where;
                if (next == sink) {
                    break;
                }
            }
        }
    }

    // we compute the path capacity
    int pathCap = INF;
    where = sink;
    while (from[where] != -1) {
        int prev = from[where]; // the prev vertex
        pathCap = min(pathCap, capacity[prev][where]);
        where = prev;
    }

    // we update the residual network; if no path is found the while
    // loop will not be entered
    where = sink;
    while (from[where] > -1) {
        int prev = from[where];
        capacity[prev][where] -= pathCap;
        capacity[where][prev] += pathCap;
        where = prev;
    }

    // if no path is found, path_cap is infinity
    if (pathCap == INF) {
        return 0;
    } else {
        return pathCap;
    }
}

int maxFlow(const int source, const int sink) {
    int result = 0, pathCap;
    do {
        pathCap = findPath(source, sink);
        if (pathCap != 0) {
            result += pathCap;
        }
    } while (pathCap != 0);

    return result;
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    int N; scanf("%d", &N);
    int SSOURCE = 0;
    int SSINK = 2 * N + 1;
    for (int v = 1; v <= N; v++) {
        int degOut, degIn;
        scanf("%d %d\n", &degOut, &degIn);

        adjacent[SSOURCE].push_back(v);
        adjacent[v].push_back(SSOURCE);
        capacity[SSOURCE][v] = degOut;

	    int u = v + N;
        adjacent[u].push_back(SSINK);
        adjacent[SSINK].push_back(u);
        capacity[u][SSINK] = degIn;

        // formeaza drum catre fiecare alt oras
        for (int u = N + 1; u <= 2 * N; u++) {
            if (u == (v + N)) continue;

            adjacent[v].push_back(u);
            adjacent[u].push_back(v);
            capacity[v][u] = 1;
        }
    }

    printf("%d\n", maxFlow(SSOURCE, SSINK));
	for (int v = 1; v <= N; v++) {
		for (int u: adjacent[v]) {
			if (capacity[v][u] == 0 && capacity[u][v] == 1 && u != SSINK) {
				printf("%d %d\n", v, u - N);
			}
		}
	}
    return 0;
}