Pagini recente » Borderou de evaluare (job #133074) | Borderou de evaluare (job #1569108) | Borderou de evaluare (job #2019466) | Borderou de evaluare (job #1736173) | Cod sursa (job #2958309)
#include <fstream>
#include <limits>
#include <queue>
#include <vector>
#include <iostream>
using std::vector;
using Node = int;
const int INF = std::numeric_limits<int>::max();
class FlowNetwork {
private:
int nodeCount;
vector<vector<int>> capacityMatrix;
vector<vector<int>> flowMatrix;
vector<vector<Node>> adjList;
void buildBfsTree(Node s, Node t, vector<Node> &prevInTree) {
std::fill(prevInTree.begin(), prevInTree.end(), -1);
prevInTree[s] = -2;
std::queue<Node> bfsQueue;
bfsQueue.push(s);
while (!bfsQueue.empty()) {
auto node = bfsQueue.front();
bfsQueue.pop();
for (Node next: adjList[node]) {
// Skip visited nodes and saturated edges
if (prevInTree[next] != -1 || flowMatrix[node][next] == capacityMatrix[node][next])
continue;
if (next == t)
continue;
prevInTree[next] = node;
bfsQueue.push(next);
}
}
}
/// Find the minimum capacity through the path from start to end
int findMinFlowThroughPath(Node start, Node end, vector<Node> &prevInPath) {
int flow = INF;
Node current = end;
while (current != start) {
Node prevNode = prevInPath[current];
flow = std::min(flow, capacityMatrix[prevNode][current] - flowMatrix[prevNode][current]);
current = prevNode;
}
return flow;
}
/// Update the flows through the path from start to end with the given value
void updateFlowThroughPath(Node start, Node end, vector<Node> &prevInPath, int flow) {
Node current = end;
while (current != start) {
Node prev = prevInPath[current];
flowMatrix[prev][current] += flow;
flowMatrix[current][prev] -= flow;
current = prev;
}
}
/// Try to find an augmenting path and return the added flow
int tryAugmentFlow(Node s, Node t, vector<Node> &prevInTree) {
buildBfsTree(s, t, prevInTree);
int totalAugmentingFlow = 0;
// For each node just before t, join it with t and use that as an augmenting path
for (Node nodeBeforeT: adjList[t]) {
// Skip node if it was unreachable due to saturation
if (prevInTree[nodeBeforeT] == -1)
continue;
// Join nodeBeforeT and t and update the capacities through the path
prevInTree[t] = nodeBeforeT;
auto minFlowThroughPath = findMinFlowThroughPath(s, t, prevInTree);
updateFlowThroughPath(s, t, prevInTree, minFlowThroughPath);
totalAugmentingFlow += minFlowThroughPath;
}
return totalAugmentingFlow;
}
public:
struct Edge {
Node from;
Node to;
};
explicit FlowNetwork(int nodeCount) : nodeCount(nodeCount) {
capacityMatrix.resize(nodeCount, vector<int>(nodeCount));
flowMatrix.resize(nodeCount, vector<int>(nodeCount));
adjList.resize(nodeCount);
}
void addEdge(Node from, Node to, int capacity) {
adjList[from].push_back(to);
adjList[to].push_back(from);
capacityMatrix[from][to] = capacity;
}
const vector<Node> &getNeighbors(Node from) {
return adjList[from];
}
int computeMaxFlow(Node s, Node t) {
int maxFlow = 0;
vector<Node> prevInPath(nodeCount);
int newFlow;
while ((newFlow = tryAugmentFlow(s, t, prevInPath)) > 0) {
maxFlow += newFlow;
}
return maxFlow;
}
int getEdgeFlow(Node from, Node to) {
return flowMatrix[from][to];
}
};
int main() {
std::ifstream in("harta.in");
int townCount;
in >> townCount;
int nodeCount = 2 * townCount + 2;
FlowNetwork network(nodeCount);
Node s = 0;
Node t = nodeCount - 1;
for (Node town = 1; town <= townCount; ++town) {
int outDegree, inDegree;
in >> outDegree >> inDegree;
// Connect s to the town
network.addEdge(s, town, outDegree);
// And t to its clone
Node townClone = town + townCount;
network.addEdge(townClone, t, inDegree);
// Connect the town with all other clones
for (Node otherTown = 1; otherTown <= townCount; ++otherTown) {
if (town == otherTown) continue;
Node clone = otherTown + townCount;
network.addEdge(town, clone, 1);
}
}
in.close();
network.computeMaxFlow(s, t);
// The roads are the saturated edges between towns and clones
vector<FlowNetwork::Edge> edges;
for (Node town = 1; town <= townCount; ++town) {
for (Node otherTown = 1; otherTown <= townCount; ++otherTown) {
if (town == otherTown) continue;
Node clone = otherTown + townCount;
if (network.getEdgeFlow(town, clone) == 1) {
edges.push_back({town, otherTown});
}
}
}
std::ofstream out("harta.out");
out << edges.size() << '\n';
for (auto [from, to] : edges) {
out << from << ' ' << to << '\n';
}
out.close();
return 0;
}