Pagini recente » Cod sursa (job #3203826) | Cod sursa (job #2961254)
#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 Flow = 0, Bottleneck, X;
memset(Seen, 0, sizeof(int) * (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(!Seen[newX] && Graph[X][newX] > 0)
{
Q.push(newX);
Seen[newX] = 1;
Father[newX] = X;
if(newX == Destination)
return 1;
}
}
}
return 0;
// for(int Node : Edges[Destination])
// {
// if(!Seen[Node])
// continue;
// X = Node;
// Bottleneck = Graph[X][Destination];
// while(Father[X] != -1)
// {
// Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
// X = Father[X];
// }
// Flow += Bottleneck;
// X = Node;
// Graph[X][Destination] -= Bottleneck;
// Graph[Destination][X] += Bottleneck;
// while(Father[X] != -1)
// {
// Graph[Father[X]][X] -= Bottleneck;
// Graph[X][Father[X]] += Bottleneck;
// X = Father[X];
// }
// }
// return Flow;
}
void MaxFlow()
{
int X, Bottleneck;
while(BFS())
{
X = Father[Destination];
Bottleneck = Graph[X][Destination];
while(Father[X] != -1)
{
Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
X = Father[X];
}
TotalFlow += Bottleneck;
X = Destination;
while(Father[X] != -1)
{
Graph[Father[X]][X] -= Bottleneck;
Graph[X][Father[X]] += Bottleneck;
X = Father[X];
}
}
}
void PrintEdges()
{
for(int i = 1; i <= N; i++)
for(int j = N + 1; j < Destination; j++)
if(Graph[i][j] == 0 && i + N != j)
out << i << ' ' << j - N << '\n';
}
int main()
{
int inDegree, outDegree;
in >> N;
Destination = N + 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);
MaxFlow();
out << TotalFlow << '\n';
PrintEdges();
}