Pagini recente » Cod sursa (job #1564746) | Cod sursa (job #108964) | Cod sursa (job #930469) | Cod sursa (job #1569104) | Cod sursa (job #3193600)
#include <fstream>
#include <utility>
#include <vector>
class Graph {
const int n, src, dest, max_size;
std::vector<std::vector<int>> adj, flow, cap;
std::vector<int> s, t;
std::vector<bool> visited;
void init(std::vector<std::pair<int, int>> roads) {
for (int i = 1; i <= n; ++i) {
int in = roads[i - 1].second, out = roads[i - 1].first;
adj[src].emplace_back(i);
adj[i].emplace_back(src);
cap[src][i] = out;
adj[n + i].emplace_back(dest);
adj[dest].emplace_back(n + i);
cap[n + i][dest] = in;
}
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j <= 2 * n; ++j) {
if (j != n + i) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
cap[i][j] = 1;
}
}
}
}
bool bfs() {
visited.assign(max_size, false);
visited[src] = true;
int start = 1, end = 1;
s[src] = 0;
t[src] = -1;
while (start <= end) {
int curr = s[start++];
for (int i = 0; i < adj[curr].size(); ++i) {
int next = adj[curr][i];
if (!visited[next] && cap[curr][next] - flow[curr][next] > 0) {
visited[next] = true;
s[++end] = next;
t[next] = curr;
if (next == dest) {
return true;
}
}
}
}
return false;
}
public:
Graph(int n, std::vector<std::pair<int, int>> roads)
: n{n}, src{0}, dest{2 * n + 1}, max_size{2 * n + 2} {
adj.assign(max_size, std::vector<int>());
flow.assign(max_size, std::vector<int>(max_size, 0));
cap.assign(max_size, std::vector<int>(max_size, 0));
s.assign(max_size, 0);
t.assign(max_size, 0);
init(roads);
}
std::vector<std::pair<int, int>> get_ans() {
while (bfs()) {
for (int i = 0; i < adj[dest].size(); ++i) {
int next = adj[dest][i];
if (visited[next] && flow[next][dest] < cap[next][dest]) {
int min = cap[next][dest] - flow[next][dest];
int curr = next;
while (t[curr] != -1) {
min = std::min(min, cap[t[curr]][curr] - flow[t[curr]][curr]);
curr = t[curr];
}
flow[next][dest] += min;
flow[dest][next] -= min;
curr = next;
while (t[curr] != -1) {
flow[t[curr]][curr] += min;
flow[curr][t[curr]] -= min;
curr = t[curr];
}
}
}
}
std::vector<std::pair<int, int>> ans;
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j <= 2 * n; ++j) {
if (flow[i][j] == 1) {
ans.emplace_back(std::make_pair(i, j - n));
}
}
}
return ans;
}
};
int main() {
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
int n;
fin >> n;
std::vector<std::pair<int, int>> roads;
for (int i = 0; i < n; ++i) {
int in, out;
fin >> out >> in;
roads.emplace_back(std::make_pair(out, in));
}
Graph g(n, roads);
std::vector<std::pair<int, int>> ans = g.get_ans();
fout << ans.size() << "\n";
for (auto it : ans) {
fout << it.first << " " << it.second << "\n";
}
fin.close();
fout.close();
return 0;
}