Pagini recente » Cod sursa (job #2568336) | Cod sursa (job #373073) | Cod sursa (job #2670701) | Cod sursa (job #1170142) | Cod sursa (job #3189632)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <iostream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Edge {
int to;
int flow;
int capacity;
int reverse;
};
class Network {
int V;
int source, sink;
vector<int> ptr;
vector<int> level;
vector<vector<Edge>> adj;
public:
Network(int V, int source = -1, int sink = -1) {
this->V = V;
this->source = source == -1 ? 0 : source;
this->sink = sink == -1 ? V - 1 : sink;
adj.resize(V);
level.resize(V, -1);
ptr.resize(V);
}
void addEdge(int u, int v, int capacity) {
Edge a{v, 0, capacity, (int)adj[v].size()};
Edge b{u, 0, 0, (int)adj[u].size()};
adj[u].push_back(a);
adj[v].push_back(b);
}
bool BFS();
int DFS(int node, int bottleneck, int t);
int getMaxFlow();
vector<pair<int, int>> getMatches();
};
bool Network::BFS() {
level.assign(V, -1);
level[source] = 0;
queue<int> q;
q.emplace(source);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &edge: adj[u]) {
if (level[edge.to] == -1 && edge.flow < edge.capacity) {
level[edge.to] = level[u] + 1;
q.emplace(edge.to);
}
}
}
return level[sink] != -1;
}
int Network::DFS(int node, int bottleneck, int dest) {
if (node == dest) {
return bottleneck;
}
for (; ptr[node] < adj[node].size(); ptr[node]++) {
Edge &e = adj[node][ptr[node]];
if (level[e.to] == level[node] + 1 && e.flow < e.capacity) {
int currBottleneck = min(bottleneck, e.capacity - e.flow);
int updatedBottleneck = DFS(e.to, currBottleneck, dest);
if (updatedBottleneck > 0) {
e.flow += updatedBottleneck;
adj[e.to][e.reverse].flow -= updatedBottleneck;
return updatedBottleneck;
}
}
}
return 0;
}
int Network::getMaxFlow() {
int totalFlow = 0, bottleneck;
while (BFS()) {
ptr.assign(V, 0);
while (bottleneck = DFS(source, INT_MAX, sink)) {
totalFlow += bottleneck;
}
}
return totalFlow;
}
vector<pair<int, int>> Network::getMatches() {
vector<pair<int, int>> matches;
for (int i = 0; i < (V - 2) / 2; ++i) {
for (auto &neighEdge: adj[i]) {
if (neighEdge.flow == 1 && neighEdge.to != source && neighEdge.to != sink) {
matches.emplace_back(i, neighEdge.to);
}
}
}
return matches;
}
int main()
{
int N;
fin >> N;
int src = 2 * N, dest = 2 * N + 1;
Network network(2 * N + 2, src, dest);
for (int i = 0; i < N; ++i) {
for (int j = N; j < 2 * N; ++j) {
if (i != j - N) {
network.addEdge(i, j, 1);
}
}
}
int x, y;
for (int i = 0; i < N; ++i) {
fin >> x >> y;
network.addEdge(src, i, x);
network.addEdge(i + N, dest, y);
}
network.getMaxFlow();
auto answer = network.getMatches();
fout << answer.size() << endl;
for (auto &x: answer) {
fout << x.first + 1 << " " << x.second + 1 - N << '\n';
}
return 0;
}