Pagini recente » Cod sursa (job #696397) | Cod sursa (job #3282530) | Cod sursa (job #56975) | Cod sursa (job #1155803) | Cod sursa (job #2961995)
#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()
{
vector < pair < int, int > > Solution;
for (int i = 1; i <= N; i++)
for (int j = N + 1; j < Destination; j++)
if (Graph[j][i])
Solution.push_back({i, j - N});
out << Solution.size() << '\n';
for(pair < int, int > &it : Solution)
out << it.first << ' ' << it.second << '\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);
while (BFS());
PrintEdges();
}