Pagini recente » Cod sursa (job #2806801) | Cod sursa (job #2696452) | Cod sursa (job #2897172) | Cod sursa (job #1122817) | Cod sursa (job #2961200)
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;
int capacitate[201][201], n;
vector<int> graf[2001];
int tata[201], viz[201];
ifstream fin("harta.in");
ofstream fout("harta.out");
int BFS()
{
queue<int> q;
memset(tata, 0, sizeof(tata));
memset(viz, 0, sizeof(viz));
q.push(0);
viz[0] = 1;
tata[0] = -1;
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == 2 * n + 1)
return 1;
for (auto i = 0; i < graf[u].size(); i++)
{
int v = graf[u][i];
if (capacitate[u][v] > 0 && !viz[v])
{
tata[v] = u;
viz[v] = 1;
q.push(v);
}
}
}
return 0;
}
int EdmondsKarp()
{
int fluxMax = 0, fluxMin, curent, adiacent;
while (BFS() == true)
{
for (auto i = 0; i < graf[2 * n + 1].size(); i++)
{
curent = graf[2 * n + 1][i];
if (capacitate[curent][2 * n + 1] > 0 && viz[curent])
{
fluxMin = capacitate[curent][2 * n + 1];
while (tata[curent] != -1)
{
adiacent = tata[curent];
fluxMin = min(fluxMin, capacitate[adiacent][curent]);
curent = adiacent;
}
fluxMax += fluxMin;
curent = graf[2 * n + 1][i];
capacitate[curent][2 * n + 1] -= fluxMin;
capacitate[2 * n + 1][curent] += fluxMin;
while (tata[curent] != -1)
{
adiacent = tata[curent];
capacitate[adiacent][curent] = capacitate[adiacent][curent] - fluxMin;
capacitate[curent][adiacent] += capacitate[curent][adiacent] + fluxMin;
curent = adiacent;
}
}
}
}
return fluxMax;
}
int main()
{
int x, y;
fin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
{
graf[i].push_back(j + n);
graf[j + n].push_back(i);
capacitate[i][j + n] = 1;
}
for (int i = 1; i <= n; i++)
{
fin >> x >> y;
graf[0].push_back(i);
graf[i].push_back(0);
capacitate[0][i] = x;
graf[2 * n + 1].push_back(i + n);
graf[i + n].push_back(2 * n + 1);
capacitate[i + n][2 * n + 1] = y;
}
fout << EdmondsKarp() << "\n";
for (int i = 1; i <= n; i++)
for (int j = n + 1; j <= 2 * n; j++)
if (capacitate[j][i] == 1)
fout << i << " " << j - n << "\n";
return 0;
}