Pagini recente » Cod sursa (job #1248111) | Cod sursa (job #1393748) | Cod sursa (job #2902935) | Cod sursa (job #3203493) | Cod sursa (job #2204062)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int kNmax = 205;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int cities;
vector<int> adj[kNmax];
int C[kNmax][kNmax];
int F[kNmax][kNmax];
void read_input() {
ifstream fin("harta.in");
fin >> cities;
n = 2*cities + 2;
memset(C, 0, sizeof C);
memset(C, 0, sizeof F);
for (int i = 2, ins, outs; i <= cities + 1; i++) {
fin >> outs >> ins;
adj[1].push_back(i);
adj[i].push_back(1);
C[1][i] += outs;
adj[cities + i].push_back(n);
adj[n].push_back(cities + 1);
C[cities + i][n] += ins;
}
for (int i = 2; i <= cities + 1; i++)
for (int j = 2; j <= cities + 1; j++) {
if (i == j) continue;
adj[i].push_back(cities + j);
adj[cities + j].push_back(i);
C[i][cities + j] = 1;
}
fin.close();
}
int get_result() {
int flow = 0;
while(1) {
queue<int> q;
vector<int> pred(n + 1, 0);
vector<int> plus(n + 1, 0);
q.push(1);
plus[1] = 2147000000;
while(!q.empty() && pred[n] == 0) {
int u = q.front();
q.pop();
for (auto v : adj[u])
if (!pred[v] && C[u][v] - F[u][v] > 0) {
q.push(v);
pred[v] = u;
plus[v] = min(plus[u], C[u][v] - F[u][v]);
}
}
if(!pred[n]) break;
int added = plus[n];
flow += added;
for(int v = n; v != 1; v = pred[v]) {
int u = pred[v];
F[u][v] += added;
F[v][u] -= added;
}
}
return flow;
}
void print_output(int result) {
ofstream fout("harta.out");
fout << result << '\n';
for (int i = 2; i <= cities + 1; i++)
for (int j = 2; j <= cities + 1; j++)
if (F[i][cities + j] == 1)
fout << i - 1 << ' ' << j - 1 << '\n';
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}