Pagini recente » Cod sursa (job #880368) | Cod sursa (job #2521036) | Cod sursa (job #1597456) | Cod sursa (job #1984437) | Cod sursa (job #2962247)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, m, s, t;
vector <vector<int>> v;
vector <int> parrent;
vector <bool> visited;
void init() {
t = 2 * n + 1;
v = vector <vector<int>> (t + 1, vector <int> (t + 1));
parrent = vector <int> (t + 1);
visited = vector <bool> (t + 1);
}
void read() {
fin >> n;
init();
int x, y;
for(int i = 1; i <= n; i ++) {
fin >> x >> y;
v[s][i] = x;
v[n + i][t] = y;
for(int j = 1; j <= n; j++)
if(i != j)
v[i][n + j] = 1;
}
}
bool bfs() {
fill(visited.begin(), visited.end(), 0);
fill(parrent.begin(), parrent.end(), 0);
queue <int> q;
q.push(s);
visited[s] = true;
int node;
while(!q.empty()) {
node = q.front();
q.pop();
if(node == t)
continue;
for(int i = 1; i <= t; i ++) {
if(!visited[i] && v[node][i]) {
parrent[i] = node;
visited[i] = true;
q.push(i);
}
}
}
return visited[t];
}
int getMaxFlow() {
int ansFlow = 0;
while(bfs()) {
for(int i = 1; i <= n; i ++) {
if(!visited[n + i])
continue;
int minFlow = 2e9;
parrent[t] = n + i;
for (int node = t; node != s; node = parrent[node]) {
if (v[parrent[node]][node] < minFlow)
minFlow = v[parrent[node]][node];
}
if(minFlow == 0)
continue;
ansFlow += minFlow;
for (int node = t; node != s; node = parrent[node]) {
v[parrent[node]][node] -= minFlow;
v[node][parrent[node]] += minFlow;
}
}
}
return ansFlow;
}
void solve() {
fout << getMaxFlow() << '\n';
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(!v[i][n + j]&& i != j)
fout << i << " " << j << '\n';
}
int main() {
read();
solve();
}