Pagini recente » Cod sursa (job #1469378) | Borderou de evaluare (job #1139926) | Diferente pentru utilizator/scipianus intre reviziile 117 si 118 | Cod sursa (job #2936811)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <iostream>
using namespace std;
ifstream in ("harta.in");
ofstream out ("harta.out");
const int max_size = 2e2 + 8, INF = 1e9 + 1;
int cap[max_size][max_size], t[max_size], intra[max_size], pleaca[max_size], n;
vector <int> mc[max_size];
bitset <max_size> viz;
bool bfs ()
{
for (int i = 1; i <= 2 * n + 2; i++)
{
viz[i] = 0;
t[i] = 0;
}
viz[1] = 1;
queue <int> q;
q.push(1);
while (!q.empty())
{
int nod = q.front();
q.pop();
for (auto f : mc[nod])
{
if (!viz[f] && cap[nod][f] > 0)
{
viz[f] = 1;
t[f] = nod;
if (f == 2 * n + 2)
{
return true;
}
q.push(f);
}
}
}
return false;
}
int main ()
{
in >> n;
for (int i = 1; i <= n; i++)
{
in >> pleaca[i] >> intra[i];
}
for (int i = 1; i <= n; i++)
{
mc[1].push_back(i + 1);
mc[i + 1].push_back(1);
mc[i + n + 1].push_back(2 * n + 2);
mc[2 * n + 2].push_back(i + n + 1);
cap[1][i + 1] = pleaca[i];
cap[i + n + 1][2 * n + 2] = intra[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
mc[i + 1].push_back(j + n + 1);
mc[j + n + 1].push_back(i + 1);
cap[i + 1][j + n + 1] = 1;
}
}
}
int maxflow = 0;
while (bfs())
{
//cout << "x"; afisare de proba
for (auto f : mc[2 * n + 2])
{
if (!viz[f] || cap[f][2 * n + 2] <= 0)
continue;
int nod = 2 * n + 2, min1 = INF;
t[nod] = f;
while (nod != 1)
{
min1 = min(min1, cap[t[nod]][nod]);
nod = t[nod];
}
if (min1 <= 0)
continue;
maxflow += min1;
nod = 2 * n + 2;
while (nod != 1)
{
cap[t[nod]][nod] -= min1;
cap[nod][t[nod]] += min1;
nod = t[nod];
}
}
}
out << maxflow << '\n';
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (cap[i + 1][j + n + 1] == 0 && cap[j + n + 1][i + 1] != 0)
{
out << i << " " << j << '\n';
}
}
}
in.close();
out.close();
return 0;
}