Pagini recente » Cod sursa (job #299260) | Cod sursa (job #2878112) | Cod sursa (job #2189827) | Cod sursa (job #3208778) | Cod sursa (job #2962716)
#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, cap;
vector <int> parrent;
vector <bool> visited;
void init() {
t = 2 * n + 1;
cap = vector <vector<int>> (t + 1, vector <int> (t + 1));
v = vector <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 ++)
for(int j = 1; j <= n; j ++)
if(i != j) {
v[i].push_back(j + n);
v[j + n].push_back(i);
cap[i][j + n] = 1;
}
for(int i = 1; i <= n; i ++) {
fin >> x >> y;
v[s].push_back(i);
v[i].push_back(s);
cap[s][i] = x;
v[i + n].push_back(t);
v[t].push_back(i + n);
cap[i + n][t] = y;
}
/*
for(int i = 1; i <= t; i ++, cout << '\n') {
cout << i << " : ";
for (const auto &node: v[i])
cout << node << " ";
}
cout << '\n';
for(int i = 1; i <= t; i ++, cout << '\n')
for(int j = 1; j <= t; j ++)
cout << cap[i][j] << " ";
*/
}
bool bfs() {
fill(visited.begin(), visited.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(const auto& i : v[node]) {
if(!visited[i] && cap[node][i]) {
parrent[i] = node;
visited[i] = true;
q.push(i);
}
}
}
return visited[t];
}
int getMaxFlow() {
int ansFlow = 0;
while(bfs()) {
for(const auto& i : v[t]) {
if(!visited[i])
continue;
int minFlow = 2e9;
parrent[t] = i;
for (int node = t; node != s; node = parrent[node]) {
if (cap[parrent[node]][node] < minFlow)
minFlow = cap[parrent[node]][node];
}
if(minFlow == 0)
continue;
ansFlow += minFlow;
for (int node = t; node != s; node = parrent[node]) {
cap[parrent[node]][node] -= minFlow;
cap[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(i != j && !cap[i][n + j])
fout << i << " " << j << '\n';
}
int main() {
read();
solve();
}
///Complexitate O(N * M^2)