Pagini recente » Cod sursa (job #1497336) | Cod sursa (job #462129) | Cod sursa (job #1134872) | Cod sursa (job #102824) | Cod sursa (job #2613568)
#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;
vector<int> parent;
vector<bool> 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);
visited[s] = true;
fill(visited.begin(), visited.end(), false);
//memset(&visited[0], false, sizeof(visited[0]) * visited.size());
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;
parent.resize(N + 2, -1);
visited.resize(N + 2, false);
bool result = false;
while (true) {
result = bfs();
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;
}