Pagini recente » Cod sursa (job #1264495) | Cod sursa (job #2514514) | Cod sursa (job #96092) | Cod sursa (job #1194484) | Cod sursa (job #2966929)
#include <bits/stdc++.h>
using namespace std;
// Complexitate O(N * M^2)
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, m, s, t;
vector <vector<int>> v, cap;
vector <int> tata;
vector <bool> visited;
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]) {
tata[i] = node;
visited[i] = true;
q.push(i);
}
}
}
return visited[t];
}
int getMaxFlow() {
int F = 0;
while(bfs()) {
for(const auto& i : v[t]) {
if(!visited[i])
continue;
int minFlow = 2e9;
tata[t] = i;
for (int node = t; node != s; node = tata[node]) {
// gaseste capacitatea minima a muchiilor
if (cap[tata[node]][node] < minFlow)
minFlow = cap[tata[node]][node];
}
if(minFlow == 0)
continue;
F += minFlow;
//parcurgere drum pt a actualiza capacitatile muchiilor
for (int node = t; node != s; node = tata[node]) {
cap[tata[node]][node] -= minFlow;
cap[node][tata[node]] += minFlow;
}
}
}
return F;
}
int main() {
fin >> n;
t = 2 * n + 1;
cap = vector <vector<int>> (t + 1, vector <int> (t + 1));
v = vector <vector <int>> (t + 1);
tata = vector <int> (t + 1);
visited = vector <bool> (t + 1);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i != j) {
v[i].push_back(j + n); // adauga o muchie de la nodul i la nodul j+n cu cap 1
v[j + n].push_back(i);
cap[i][j + n] = 1;
}
int x, y;
for(int i = 1; i <= n; i ++) {
fin >> x >> y;
v[s].push_back(i); // adauga muchie de la nodul sursa la nodul i cu capacitate x
v[i].push_back(s);
cap[s][i] = x;
v[i + n].push_back(t); //adauga muchie de la nodul cu capacitaete y la nodul destinatie
v[t].push_back(i + n);
cap[i + n][t] = y;
}
fout << getMaxFlow() << '\n';
//daca nu exista nici o capacitate pe marginea dintre nodul curent si nodul adiacent
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';
return 0;
}