Pagini recente » Cod sursa (job #1367414) | Cod sursa (job #1334623) | Cod sursa (job #3287681) | Cod sursa (job #1316052) | Cod sursa (job #2961195)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
int capacity[201][201];
vector<int> l[2001];
int tata[201] = { 0 }, viz[202] = { 0 };
///nr de muchii
int n;
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 (int i = 0; i < l[u].size(); i++)
{
int v = l[u][i];
if (capacity[u][v] > 0 && !viz[v])
{
tata[v] = u;
viz[v] = 1;
q.push(v);
}
}
}
return 0;
}
int edmonds_karp()
{
int maxim = 0, minim, u, v;
while (bfs())
{
for (int i = 0; i < l[2 * n + 1].size(); i++)
{
u = l[2 * n + 1][i];
if (capacity[u][2 * n + 1] > 0 && viz[u])
{
minim = capacity[u][2 * n + 1];
while (tata[u] != -1)
{
v = tata[u];
minim = min(minim, capacity[v][u]);
u = v;
}
maxim += minim;
u = l[2 * n + 1][i];
capacity[u][2 * n + 1] -= minim;
capacity[2 * n + 1][u] += minim;
while (tata[u] != -1)
{
v = tata[u];
capacity[v][u] -= minim;
capacity[u][v] += minim;
u = v;
}
}
}
}
return maxim;
}
int main()
{
int di, de;
in >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
{
l[i].push_back(j + n);
l[j + n].push_back(i);
capacity[i][j + n] = 1;
}
for (int i = 1; i <= n; i++)
{
in >> di >> de;
l[0].push_back(i);
l[i].push_back(0);
capacity[0][i] = di;
l[2 * n + 1].push_back(i + n);
l[i + n].push_back(2 * n + 1);
capacity[i + n][2 * n + 1] = de;
}
out << edmonds_karp() << "\n";
for (int i = 1; i <= n; i++)
for (int j = n + 1; j <= 2 * n; j++)
if (capacity[j][i] == 1)
out << i << " " << j - n << "\n";
return 0;
}