Pagini recente » Concursuri | Cod sursa (job #2357321) | Cod sursa (job #361712) | Cod sursa (job #410870) | Cod sursa (job #2959992)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, m, x, y, capacitate, mat[1001][1001];
queue <int> q;
bool visited[1001];
int parinte[1001];
bool bfs() {
while (!q.empty())
q.pop();
for (int i = 0; i <= 2 * n + 1; ++i) {
parinte[i] = -1;
visited[i] = false;
}
q.push(0);
visited[0] = true;
while (!q.empty()) {
int nod = q.front();
q.pop();
if (nod == 2 * n + 1)
return true;
for (int i = 1; i <= 2 * n + 1; ++i)
if (visited[i] == false && mat[nod][i] > 0) {
q.push(i);
visited[i] = true;
parinte[i] = nod;
}
}
return false;
}
int fluxMax() {
int maxFlow = 0;
while (bfs()) {
for (int i = n + 1; i < 2 * n + 1; i++) {
if (mat[i][2 * n + 1] > 0 && visited[i] == true) {
int frunza = i;
vector <int> drum;
drum.push_back(2 * n + 1);
drum.push_back(frunza);
int nod = parinte[frunza];
if (nod == 0)
drum.push_back(nod);
else {
while (nod != 0) {
drum.push_back(nod);
nod = parinte[nod];
}
drum.push_back(0);
}
reverse(drum.begin(), drum.end());
int minCap = 2e9;
for (int i = 0; i < drum.size() - 1; i++)
minCap = min(minCap, mat[drum[i]][drum[i+1]]);
maxFlow += minCap;
for (int i = 0; i < drum.size() - 1; i++) {
mat[drum[i]][drum[i + 1]] -= minCap;
mat[drum[i + 1]][drum[i]] += minCap;
}
}
}
}
return maxFlow;
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> x >> y;
mat[0][i] = x;
mat[n + i][2 * n + 1] = y;
for (int nod = 1; nod <= n; nod++)
if (nod != i)
mat[i][n + nod] = 1;
}
fout << fluxMax() << endl;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mat[i][n + j] == 0 && i != j)
fout << i << " " << j << endl;
return 0;
}