Pagini recente » Cod sursa (job #3336807) | Cod sursa (job #3323808) | Cod sursa (job #273559) | Cod sursa (job #1059296) | Cod sursa (job #3329912)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 205;
int capacitate[NMAX][NMAX];
int flux[NMAX][NMAX];
int parinte[NMAX];
vector<int> G[NMAX];
int N;
bool bfs(int s, int d) {
memset(parinte, 0, sizeof(parinte));
vector<int> vis(NMAX, 0);
queue<int> q;
q.push(s);
vis[s] = 1;
parinte[s] = -1; // radacina
while(!q.empty()) {
int nod = q.front();
q.pop();
if (nod == d) return true;
for(int vecin : G[nod]) {
if(!vis[vecin] && capacitate[nod][vecin] - flux[nod][vecin] > 0) {
vis[vecin] = 1;
parinte[vecin] = nod;
q.push(vecin);
}
}
}
return false;
}
int main() {
fin >> N;
int S = 0;
int D = 2 * N + 1;
for(int i = 1; i <= N; i++) {
int out_deg, in_deg;
fin >> out_deg >> in_deg;
capacitate[S][i] = out_deg;
G[S].push_back(i);
G[i].push_back(S);
capacitate[N + i][D] = in_deg;
G[N + i].push_back(D);
G[D].push_back(N + i);
for(int j = 1; j <= N; j++) {
if(i != j) {
capacitate[i][N + j] = 1;
G[i].push_back(N + j);
G[N + j].push_back(i);
}
}
}
int max_flow = 0;
while(bfs(S, D)) {
int path_flow = 1e9;
for(int nod = D; nod != S; nod = parinte[nod]) {
int prev = parinte[nod];
path_flow = min(path_flow, capacitate[prev][nod] - flux[prev][nod]);
}
for(int nod = D; nod != S; nod = parinte[nod]) {
int prev = parinte[nod];
flux[prev][nod] += path_flow;
flux[nod][prev] -= path_flow;
}
max_flow += path_flow;
}
fout << max_flow << '\n';
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if (i == j) continue;
if (flux[i][N + j] == 1) {
fout << i << " " << j << '\n';
}
}
}
return 0;
}