Pagini recente » Cod sursa (job #2261520) | Cod sursa (job #1134755) | Cod sursa (job #3218514) | Cod sursa (job #2934476) | Cod sursa (job #3191644)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <climits>
using namespace std;
class FlowNetwork {
private:
static const int Nmax = 301;
static const int INF = INT_MAX;
int N;
int S, D;
vector<vector<int>> capacity, flow;
vector<vector<int>> graph;
vector<int> parent;
public:
FlowNetwork() : N(0), S(0), D(300) {}
void readGraph(const string &filename) {
ifstream inputFile(filename);
inputFile >> N;
initializeGraph();
int a, b;
for (int i = 1; i <= N; ++i) {
inputFile >> a >> b;
addEdge(0, i, a);
addEdge(i + N, D, b);
addEdge(D, i + N, 0);
}
inputFile.close();
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (i != j && capacity[0][i] && capacity[j + N][D])
addEdge(i, j + N, 1);
}
void solveMaxFlow() {
while (bfs()) {
augmentPath();
}
}
void writeResults(const string &filename) {
ofstream outputFile(filename);
vector<pair<int, int>> solution;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (flow[i][j + N] > 0)
solution.emplace_back(i, j);
outputFile << solution.size() << "\n";
for (const auto &edge: solution)
outputFile << edge.first << " " << edge.second << "\n";
outputFile.close();
}
private:
void initializeGraph() {
capacity.assign(Nmax, vector<int>(Nmax, 0));
flow.assign(Nmax, vector<int>(Nmax, 0));
graph.assign(Nmax, vector<int>());
parent.assign(Nmax, -1);
}
void addEdge(int from, int to, int cap) {
graph[from].push_back(to);
graph[to].push_back(from);
capacity[from][to] = cap;
}
bool bfs() {
queue<int> Q;
bitset<Nmax> visited;
Q.push(S);
visited[S] = true;
while (!Q.empty()) {
int currentNode = Q.front();
Q.pop();
if (currentNode == D)
continue;
for (int neighbor: graph[currentNode]) {
if (!visited[neighbor] && capacity[currentNode][neighbor] > flow[currentNode][neighbor]) {
parent[neighbor] = currentNode;
visited[neighbor] = true;
Q.push(neighbor);
}
}
}
return visited[D];
}
void augmentPath() {
int minCapacity = INF;
int current = D;
while (current != S) {
int previous = parent[current];
minCapacity = min(minCapacity, capacity[previous][current] - flow[previous][current]);
current = previous;
}
current = D;
while (current != S) {
int previous = parent[current];
flow[previous][current] += minCapacity;
flow[current][previous] -= minCapacity;
current = previous;
}
}
};
int main() {
FlowNetwork flowNetwork;
flowNetwork.readGraph("harta.in");
flowNetwork.solveMaxFlow();
flowNetwork.writeResults("harta.out");
return 0;
}