Pagini recente » Cod sursa (job #238181) | Cod sursa (job #1793228) | Cod sursa (job #59780) | Cod sursa (job #1529073) | Cod sursa (job #2613556)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int kNmax = 101;
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;
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 i = 1; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
if((j - i) != n) {
C[i][j] = 1;
}
}
}
fin.close();
}
bool bfs(int s, int t, vector<int> &parent, vector<bool> &visited) {
queue<int> q;
int u;
fill(visited.begin(), visited.end(), false);
fill(parent.begin(), parent.end(), false);
q.push(s);
visited[s] = true;
while(!q.empty()) {
u = q.front(); q.pop();
for (int v = 0; v <= t; v++) {
if (visited[v] == false && C[u][v]) {
visited[v] = true;
parent[v] = u;
q.push(v);
}
}
}
return visited[t];
}
int get_result() {
int flow = 0, aux_flow;
int current, prev;
vector<int> parent(N + 2, -1);
vector<bool> visited(N + 2, false);
bool result = false;
while (true) {
result = bfs(s, t, parent, visited);
if (!result) {
break;
}
aux_flow = (1 << 30);
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;
}