Pagini recente » Cod sursa (job #2645053) | Cod sursa (job #253507) | Cod sursa (job #2140306) | Cod sursa (job #746984) | Cod sursa (job #2961594)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int cap[202][202], n, max_flow, current_flow;
vector<int> vis, pred;
vector<vector<int>> adj;
// Parcurg graful prin BFS, cu conditia ca fluxul exuistent dintre
// doua noduri sa nu depaseasca capacitatea muchiei respective.
// De asemenea, pe langa faptul ca un anume nod este vizitat, retin
// si care este nodul din care am ajuns in acesta (predecesorul).
bool bfs()
{
fill(vis.begin(), vis.end(), 0);
fill(pred.begin(), pred.end(), 0);
vis[0] = 1;
pred[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty())
{
int c = q.front();
q.pop();
// Am ajuns in nodul destinatie.
if (c == 2 * n + 1)
return true;
for (int i = 0; i < adj[c].size(); i++)
{
if (!vis[adj[c][i]] && 0 < cap[c][adj[c][i]])
{
q.push(adj[c][i]);
pred[adj[c][i]] = c;
vis[adj[c][i]] = 1;
}
}
}
return false;
}
int main()
{
fin >> n;
// Fiecare nod din graf are doua copii, una in multimea L si una
// in multimea R.
// Nodurile din multimea L sunt numerotate de la 1 la n, iar cele
// din multimea R de la n + 1 la 2 * n.
vis.resize(2 * n + 2);
pred.resize(2 * n + 2);
adj.resize(2 * n + 2);
// Adaug pe 0 ca nod sursa si muchii intre acesta si toate nodurile
// din multimea L cu capacitatile egale cu gradele de iesire.
// Adaug pe 2 * n + 1 ca nod destinatie si muchii intre acesta si
// toate nodurile din multimea R cu capacitatile egale cu gradele
// de intrare.
// Adaug muchii intre nodurile din multimea L si R, dar nu de la
// un nod la el insusi.
for (int i = 1; i <= n; i++)
{
adj[0].push_back(i);
adj[i].push_back(0);
adj[i + n].push_back(2 * n + 1);
adj[2 * n + 1].push_back(i + n);
for (int j = n + 1; j <= 2 * n; j++)
{
if (i != j - n)
{
adj[i].push_back(j);
adj[j].push_back(i);
cap[i][j] = 1;
}
}
int x, y;
fin >> x >> y;
cap[0][i] = x;
cap[i + n][2 * n + 1] = y;
}
// Cat timp exista un drum intre sursa si destinatie.
while (bfs())
{
// Iterez prin vecinii nodului destinatie.
for (int i = 0; i < adj[2 * n + 1].size(); i++)
{
// Daca un nod vecin cu nodul destinatie este vizitat,
// inseamna ca acesta este unul dintre predecesorii nodului
// destinatie. In acest caz, exista un drum intre sursa
// si destinatie prin acest nod.
if (vis[adj[2 * n + 1][i]])
{
pred[2 * n + 1] = adj[2 * n + 1][i];
current_flow = __INT_MAX__;
// Determin care este limitarea de pe ruta
// (muchia cu capacitate minima).
for (int j = 2 * n + 1; j != 0; j = pred[j])
{
current_flow = min(current_flow, cap[pred[j]][j]);
}
// Adun fluxul curent la fluxul de pe fiecare muchie
// din lant si il scad pentru a obtine flux negativ
// pe muchiile de intoarcere.
for (int j = 2 * n + 1; j != 0; j = pred[j])
{
cap[pred[j]][j] -= current_flow;
cap[j][pred[j]] += current_flow;
}
// Adun fluxul curent la fluxul maxim.
max_flow += current_flow;
}
}
}
// Valoarea fluxului maxim coincide cu numarul de drumuri construite.
fout << max_flow << '\n';
// Afisez nodurile intre care exista o muchie saturata.
for (int i = 1; i <= n; i++)
for (int j = 1; j < adj[i].size(); j++)
if (!cap[i][adj[i][j]])
fout << i << ' ' << adj[i][j] - n << '\n';
return 0;
}