Pagini recente » Cod sursa (job #2070297) | Cod sursa (job #2622821) | Cod sursa (job #1660584) | Cod sursa (job #677179) | Cod sursa (job #3194261)
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
#define NMAX 256
vector< int >G[NMAX]; // Un vector de liste de adiacență pentru a reprezenta graful
int N, NODT; // N este numărul de noduri, NODT este nodul țintă în rețea
int C[NMAX][NMAX]; // Matricea de capacități pentru a stoca capacitățile muchiilor grafului
int pred[NMAX+4]; // Vectorul de predecesori pentru reconstruirea căilor
// Funcția Bellman-Ford pentru a găsi o cale de augmentare în rețea
bool bf() {
vector< int >::iterator it;
memset(pred, -1, sizeof(pred));
int nod;
queue < int > Q;
Q.push(0);
while (!Q.empty()) {
nod = Q.front();
if (nod == NODT) break;
for (it = G[nod].begin(); it != G[nod].end(); ++it) {
if (pred[*it] == -1 && C[nod][*it] > 0) {
Q.push(*it);
pred[*it] = nod;
}
}
Q.pop();
}
if (nod != NODT) return 1;
for (nod = NODT; nod; nod = pred[nod]) {
--C[pred[nod]][nod];
++C[nod][pred[nod]];
}
return 0;
}
// Funcție pentru a afișa rezultatul
void show() {
int i, j;
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (i != j && !C[i][j + N]) {
printf("%d %d\n", i, j);
}
}
// Funcția care rezolvă problema fluxului maximal
void solve() {
int ANS = 0;
while (!bf()) {
++ANS;
}
printf("%d\n", ANS);
show();
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &N);
NODT = (N << 1) + 2;
int i, j;
int a1, a2;
for (i = 1; i <= N; ++i) {
scanf("%d%d\n", &a1, &a2);
G[i].push_back(0);
G[0].push_back(i);
C[0][i] = a1;
G[i + N].push_back(NODT);
G[NODT].push_back(i + N);
C[i + N][NODT] = a2;
for (j = 1; j <= N; ++j) {
if (j != i) {
G[i].push_back(j + N);
G[j + N].push_back(i);
C[i][j + N] = 1;
C[j + N][i] = 0;
}
}
}
solve();
return 0;
}