Cod sursa(job #2232424)

Utilizator axelteoTeodor Dutu axelteo Data 19 august 2018 00:42:02
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>

using namespace std;

#define MAX_N 202

ifstream fIn("harta.in");
ofstream fOut("harta.out");

bool marked[MAX_N];
int dest, numVert, maxPaths, parent[MAX_N], paths[MAX_N][MAX_N];
vector<int> adjList[MAX_N];
queue<int> q;

inline bool BFS() {
    int currNode;

    while (!q.empty()) {
        q.pop();
    }

    memset(marked, 0, sizeof(marked));

    q.push(0);
    marked[0] = true;

    while (!q.empty()) {
        currNode = q.front();
        q.pop();

        if (currNode != dest) {
            for (int nextNode : adjList[currNode]) {
                if (!marked[nextNode] && paths[currNode][nextNode]) {
                    marked[nextNode] = true;
                    parent[nextNode] = currNode;
                    q.push(nextNode);
                }
            }
        }
    }

    return marked[dest];
}

int main() {
    int inDeg, outDeg, aux, currPaths;

    fIn >> numVert;
    dest = numVert * 2 + 1;

    for (register int i = 1; i <= numVert; ++i) {
        fIn >> inDeg >> outDeg;
        aux = i + numVert;

        adjList[0].emplace_back(i);
        adjList[i].emplace_back(0);
        adjList[aux].emplace_back(dest);
        adjList[dest].emplace_back(aux);

        paths[0][i] = inDeg;
        paths[aux][dest] = outDeg;
    }

    for (register int i = 1; i <= numVert; ++i) {
        for (register int j = 1; j <= numVert; ++j) {
            if (i != j) {
                aux = j + numVert;
                paths[i][aux] = 1;

                adjList[i].emplace_back(aux);
                adjList[aux].emplace_back(i);
            }
        }
    }

    while (BFS()) {
        for (int currNode : adjList[dest]) {
            if (marked[currNode]) {
                currPaths = INT_MAX;
                parent[dest] = currNode;

                for (register int i = dest; i != 0; i = parent[i]) {
                    currPaths = min(currPaths, paths[parent[i]][i]);
                }

                if (currPaths) {
                    for (register int i = dest; i != 0; i = parent[i]) {
                        paths[parent[i]][i] -= currPaths;
                        paths[i][parent[i]] += currPaths;
                    }

                    maxPaths += currPaths;
                }
            }
        }
    }

    fOut << maxPaths << '\n';

    for (register int i = 1; i <= numVert; ++i) {
        for (register int j = 1; j <= numVert; ++j) {
            if (!paths[i][j + numVert] && i != j) {
                fOut << i << ' ' << j << '\n';
            }
        }
    }

    fIn.close();
    fOut.close();
    return 0;
}