Pagini recente » Cod sursa (job #711572) | Cod sursa (job #212112) | Cod sursa (job #188293) | Cod sursa (job #3199363) | Cod sursa (job #3193715)
#include "bits/stdc++.h"
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int numNodes;
vector<vector<int>> flowCapacity;
vector<vector<int>> graph;
const int INF = 1e9;
int bfs(int source, int sink, vector<int>& parent) {
fill(parent.begin(), parent.end(), -1);
parent[source] = -2;
queue<pair<int, int>> queue;
queue.push({ source, INF });
while (!queue.empty()) {
int current = queue.front().first;
int currentFlow = queue.front().second;
queue.pop();
for (int next : graph[current]) {
if (parent[next] == -1 && flowCapacity[current][next]) {
parent[next] = current;
int newFlow = min(currentFlow, flowCapacity[current][next]);
if (next == sink)
return newFlow;
queue.push({ next, newFlow });
}
}
}
return 0;
}
int findMaxFlow(int source, int sink) {
int totalFlow = 0;
vector<int> parent(202);
int newFlow;
while (newFlow = bfs(source, sink, parent)) {
totalFlow += newFlow;
int currentNode = sink;
while (currentNode != source) {
int previousNode = parent[currentNode];
flowCapacity[previousNode][currentNode] -= newFlow;
flowCapacity[currentNode][previousNode] += newFlow;
currentNode = previousNode;
}
}
return totalFlow;
}
int main() {
fin >> numNodes;
int sourceNode = 0, sinkNode = numNodes + numNodes + 1;
flowCapacity.resize(200, vector<int>(200, 0));
graph.resize(200);
for (int i = 1; i <= numNodes; ++i) {
int out, in;
fin >> out >> in;
graph[sourceNode].push_back(i);
flowCapacity[sourceNode][i] = out;
graph[numNodes + i].push_back(sinkNode);
flowCapacity[numNodes + i][sinkNode] = in;
for (int j = 1; j <= numNodes; ++j) {
if (i == j)
continue;
graph[i].push_back(numNodes + j);
flowCapacity[i][numNodes + j] = 1;
graph[numNodes + j].push_back(i);
}
}
fout << findMaxFlow(sourceNode, sinkNode) << '\n';
for (int i = 1; i <= numNodes; ++i) {
for (int adjacentNode: graph[i]) {
if (flowCapacity[i][adjacentNode] == 0) {
fout << i << " " << adjacentNode - numNodes << '\n';
}
}
}
return 0;
}