Pagini recente » Cod sursa (job #1619140) | Cod sursa (job #568528) | Cod sursa (job #172580) | Cod sursa (job #1047647) | Cod sursa (job #1554496)
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int N_MAX = 100;
const int NODES = 2 * N_MAX + 2;
const int INF = 1e9;
ifstream fin("harta.in");
ofstream fout("harta.out");
int N, dest, cnt;
vector<int> al[NODES];
bool use[NODES];
int padre[NODES];
int capacity[NODES][NODES];
int flow[NODES][NODES];
inline void AddEdge(int x, int y, int c) {
al[x].push_back(y);
al[y].push_back(x);
capacity[x][y] = c;
}
bool Bfs() {
memset(use, 0, sizeof use);
queue<int> q;
use[0] = true;
q.push(0);
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == dest)
continue;
for (int son : al[node])
if (!use[son] && flow[node][son] < capacity[node][son]) {
padre[son] = node;
use[son] = true;
q.push(son);
}
}
return use[dest];
}
int main() {
fin >> N;
dest = 2 * N + 1;
for (int i = 1; i <= N; ++i) {
int out, in;
fin >> out >> in;
AddEdge(0, i, out);
AddEdge(N + i, dest, in);
cnt += out;
}
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (i != j)
AddEdge(i, N + j, 1);
while (Bfs()) {
for (int node : al[dest])
if (use[node] && flow[node][dest] < capacity[node][dest]) {
padre[dest] = node;
bool ok = true;
for (int i = dest; i != 0; i = padre[i])
if (flow[padre[i]][i] == capacity[padre[i]][i])
ok = false;
if (ok)
for (int i = dest; i != 0; i = padre[i]) {
++flow[padre[i]][i];
--flow[i][padre[i]];
}
}
}
fout << cnt << "\n";
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (flow[i][N + j] == 1)
fout << i << " " << j << "\n";
return 0;
}