Pagini recente » Cod sursa (job #1800153) | Cod sursa (job #1643662) | Cod sursa (job #568504) | Cod sursa (job #3183974) | Cod sursa (job #2961203)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int capacitate[201][201];
vector<int> graf[2001];
int tata[201] = { 0 }, viz[202] = { 0 };
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 < 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 maxim = 0, minim, u, v;
while (bfs())
{
for (int i = 0; i < graf[2 * n + 1].size(); i++)
{
u = graf[2 * n + 1][i];
if (capacitate[u][2 * n + 1] > 0 && viz[u])
{
minim = capacitate[u][2 * n + 1];
while (tata[u] != -1)
{
v = tata[u];
minim = min(minim, capacitate[v][u]);
u = v;
}
maxim += minim;
u = graf[2 * n + 1][i];
capacitate[u][2 * n + 1] -= minim;
capacitate[2 * n + 1][u] += minim;
while (tata[u] != -1)
{
v = tata[u];
capacitate[v][u] -= minim;
capacitate[u][v] += minim;
u = v;
}
}
}
}
return maxim;
}
int main()
{
int di, de;
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 >> di >> de;
graf[0].push_back(i);
graf[i].push_back(0);
capacitate[0][i] = di;
graf[2 * n + 1].push_back(i + n);
graf[i + n].push_back(2 * n + 1);
capacitate[i + n][2 * n + 1] = de;
}
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;
}