Pagini recente » Cod sursa (job #1920219) | Cod sursa (job #1262676) | Cod sursa (job #2879147) | Cod sursa (job #2665784) | Cod sursa (job #2961154)
#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];
queue < int > Q;
vector < int > Edges[NMAX];
int BFS()
{
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(newX == Destination)
continue;
if(!Seen[newX] && Graph[X][newX] > 0)
Q.push(newX), Seen[newX] = 1, Father[newX] = X;
}
}
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 flow = BFS();
while(flow)
{
TotalFlow += flow;
flow = BFS();
}
}
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)
continue;
else
Graph[i][j] = 1, Edges[i].push_back(j), Edges[j].push_back(i);
MaxFlow();
out << TotalFlow << '\n';
PrintEdges();
}