Pagini recente » Cod sursa (job #829552) | Cod sursa (job #3333747) | Cod sursa (job #96815) | Cod sursa (job #273554) | Cod sursa (job #3333749)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int INF = 1e9;
const int MAXN = 105;
int N;
int capacity[2 * MAXN][2 * MAXN];
int parent[2 * MAXN];
vector<int> adj[2 * MAXN];
void add_edge(int u, int v, int cap) {
adj[u].push_back(v);
adj[v].push_back(u);
capacity[u][v] = cap;
}
int bfs(int s, int t) {
fill(parent, parent + 2 * N + 2, -1);
parent[s] = -2;
queue<pair<int, int>> q;
q.push({s, INF});
while (!q.empty()) {
int u = q.front().first;
int flow = q.front().second;
q.pop();
for (int v : adj[u]) {
if (parent[v] == -1 && capacity[u][v] > 0) {
parent[v] = u;
int new_flow = min(flow, capacity[u][v]);
if (v == t)
return new_flow;
q.push({v, new_flow});
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
int new_flow;
while (new_flow = bfs(s, t)) {
flow += new_flow;
int cur = t;
while (cur != s) {
int prev = parent[cur];
capacity[prev][cur] -= new_flow;
capacity[cur][prev] += new_flow;
cur = prev;
}
}
return flow;
}
int main() {
fin >> N;
int S = 0;
int D = 2 * N + 1;
int total_edges = 0;
for (int i = 1; i <= N; ++i) {
int dout, din;
fin >> dout >> din;
add_edge(S, i, dout);
add_edge(N + i, D, din);
for (int j = 1; j <= N; ++j) {
if (i != j) {
add_edge(i, N + j, 1);
}
}
}
max_flow(S, D);
vector<pair<int, int>> result_edges;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (i == j) continue;
if (capacity[i][N + j] == 0) {
result_edges.push_back({i, j});
}
}
}
fout << result_edges.size() << "\n";
for (auto p : result_edges) {
fout << p.first << " " << p.second << "\n";
}
return 0;
}