Pagini recente » Cod sursa (job #3243308) | Cod sursa (job #2756997) | Cod sursa (job #1795482) | Cod sursa (job #36415) | Cod sursa (job #2613586)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int kNmax = 101;
const int INF = (1 << 30);
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n, N, m;
int C[2 * kNmax + 2][2 * kNmax + 2];
int s, t;
vector<int> parent;
vector<int> visited;
void read_input() {
ifstream fin("harta.in");
fin >> n;
s = 0; t = 2 * n + 1;
N = 2 * n;
memset(C, 0, sizeof C);
for (int i = 1, x, y; i <= n; i++) {
fin >> x >> y;
C[s][i] = x;
C[n + i][t] = y;
for (int j = n + 1; j <= 2 * n; j++) {
if((j - i) != n) {
C[i][j] = 1;
}
}
}
fin.close();
}
bool bfs() {
queue<int> q;
int u;
q.push(s);
memset((&visited[0]), 0, sizeof(visited[0]) * visited.size());
visited[s] = 1;
while(!q.empty()) {
u = q.front(); q.pop();
if (u == t) {
continue;
}
for (int v = 0; v <= t; v++) {
if (visited[v] == 0 && C[u][v]) {
visited[v] = 1;
parent[v] = u;
q.push(v);
}
}
}
return visited[t];
}
int get_result() {
int flow = 0, aux_flow;
int current, prev;
parent.resize(N + 2, -1);
visited.resize(N + 2, 0);
bool result = false;
while (true) {
result = bfs();
if (!result) {
break;
}
aux_flow = INF;
current = t;
while (current != s) {
prev = parent[current];
aux_flow = min(aux_flow, C[prev][current]);
current = prev;
}
current = t;
while (current != s) {
prev = parent[current];
C[prev][current] -= aux_flow;
C[current][prev] += aux_flow;
current = prev;
}
flow += aux_flow;
}
return flow;
}
void print_output(int result) {
ofstream fout("harta.out");
fout << result << '\n';
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
if ((j - i) != n && C[i][j] == 0) {
fout << i << " " << j - n << endl;
}
}
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}