Pagini recente » Cod sursa (job #3127204) | Cod sursa (job #2372703) | Cod sursa (job #1054323) | Cod sursa (job #1670600) | Cod sursa (job #2961992)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 205;
int Graph[NMAX][NMAX], N, Source, Destination, Father[NMAX], TotalFlow;
bool Seen[NMAX];
vector<int> Edges[NMAX];
bool BFS()
{
queue<int> Q;
int X, Flow = 0, Bottleneck;
memset(Seen, 0, (Destination + 1));
Seen[0] = 1;
Q.push(0);
Father[0] = -1;
while (!Q.empty())
{
X = Q.front();
Q.pop();
for (int newX : Edges[X])
{
if (newX == Destination)
continue;
if (!Seen[newX] && Graph[X][newX] != 0)
{
Father[newX] = X;
Q.push(newX);
Seen[newX] = 1;
}
}
}
for (int Node : Edges[Destination])
if (Seen[Node] && Graph[Node][Destination] > 0)
{
Father[Destination] = Node;
X = Node;
Bottleneck = Graph[X][Destination];
while (Father[X] != -1)
{
Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
X = Father[X];
}
Flow += Bottleneck;
X = Destination;
while (Father[X] != -1)
{
Graph[Father[X]][X] -= Bottleneck;
Graph[X][Father[X]] += Bottleneck;
X = Father[X];
}
}
return Flow;
}
void PrintEdges()
{
for (int i = 1; i <= N; i++)
for (int j = N + 1; j < Destination; j++)
if (Graph[j][i])
out << i << ' ' << j - N << '\n';
}
int main()
{
int inDegree, outDegree;
in >> N;
Destination = 2 * N + 1;
for (int i = 1; i <= N; i++)
{
in >> outDegree >> inDegree;
Graph[0][i] = outDegree;
Graph[i + N][Destination] = inDegree;
Edges[0].push_back(i);
Edges[i].push_back(0);
Edges[i + N].push_back(Destination);
Edges[Destination].push_back(i + N);
}
for (int i = 1; i <= N; i++)
for (int j = N + 1; j < Destination; j++)
if (i != j - N)
Graph[i][j] = 1, Edges[i].push_back(j), Edges[j].push_back(i);
inDegree = BFS();
while (inDegree)
{
TotalFlow += inDegree;
inDegree = BFS();
}
out << TotalFlow << '\n';
PrintEdges();
}