Pagini recente » Cod sursa (job #1063954) | Cod sursa (job #1931516) | Cod sursa (job #401260) | Cod sursa (job #528292) | Cod sursa (job #2232424)
#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;
}