Pagini recente » Cod sursa (job #2961126) | Cod sursa (job #2809123) | Cod sursa (job #513797) | Cod sursa (job #3180547) | Cod sursa (job #2955710)
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
/*
Idee: Adaugam un nou start si un nou final(cu muchii de capacitati egale cu gradele out, respectiv in),
si dublam nodurile, ca sa l putem lega pe fiecare cu fiecare, ca in curs, cu muchii de capacitate 1.
De aici rulam algo de flux. Fluxul maxim obtinut ne da numarul de muchii adaugate, pentru ca fiecare
are capacitate 1. Muchiile selectate sunt cele saturate, aka au ramas capacitate 0.
*/
int tata[dim], a[dim][dim], in[dim], out[dim], n, m, nod, flow, maxFlow;
bool viz[dim];
bool bfs() {
queue<int> coada;
memset(tata, 0, sizeof(tata));
memset(viz, false, sizeof(viz));
coada.push(0);
viz[0] = true;
tata[0] = -1;
while(!coada.empty()) {
int front = coada.front();
coada.pop();
if(front == 2*n + 1) {
return true;
}
for(int i = 1; i <= 2*n + 1; i++) {
if( !viz[i] && a[front][i] > 0) {
coada.push(i);
viz[i] = true;
tata[i] = front;
}
}
}
return false;
}
int main() {
fin >> n;
for(int i = 1; i <= n; i++) {
fin >> out[i] >> in[i];
a[0][i] = out[i];
a[n + i][2*n + 1] = in[i];
for(int j = 1; j <= n; j++)
if(j != i)
a[i][n + j] = 1;
}
while(bfs()) {
for(int i = 1; i <= n; i++) {
if( viz[n + i] && a[n + i][2*n + 1] > 0 ) {
flow = inf;
tata[2*n + 1] = n + i;
for(nod = 2*n + 1; nod != 0; nod = tata[nod]) {
flow = min(flow, a[ tata[nod] ][nod]);
}
if(flow == 0) continue;
for(nod = 2*n + 1; nod != 0; nod = tata[nod]) {
a[ tata[nod] ][nod] -= flow;
a[nod][ tata[nod] ] += flow;
}
maxFlow += flow;
}
}
}
fout << maxFlow << '\n';
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++)
if( a[i][n + j] == 0 && i != j)
fout << i << " " << j << '\n';
}
return 0;
}