Pagini recente » Cod sursa (job #66492) | Cod sursa (job #998434) | Cod sursa (job #566645) | Cod sursa (job #1735064) | Cod sursa (job #573691)
Cod sursa(job #573691)
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <queue>
#define alt(x) (n + x) // nodul x.in
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int N = 205;
const int Inf = 0x3f3f3f;
int n;
int d;
int edgeCount;
int fat[N];
int c[N][N];
int f[N][N];
bool viz[N];
void Read()
{
in >> n;
d = 2*n + 1; // Destinatie
for (int i = 1; i <= n; ++i)
in >> c[0][i] >> c[alt(i)][d]; // Cate drumuri intra in i si cate drumuri ies din i
}
void SetPossibleEdges()
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j)
c[i][alt(j)] = 1; // Poate exista 1 muchie intre i si j
}
bool Road()
{
queue <int> q;
memset(viz, 0, sizeof(viz));
q.push(0);
viz[0] = 1;
while (!q.empty() && !viz[d])
{
int node = q.front();
for (int next = 0; next <= d; ++next)
if (!viz[next] && c[node][next] - f[node][next] > 0)
{
viz[next] = true;
fat[next] = node;
q.push(next);
}
q.pop();
}
return viz[d];
}
void GetMaxFlow()
{
while (Road())
{
int node = d;
int minFlow = Inf;
while (node)
{
if (c[fat[node]][node] - f[fat[node]][node] < minFlow)
minFlow = c[fat[node]][node] - f[fat[node]][node];
node = fat[node];
}
node = d;
while (node)
{
f[fat[node]][node] += minFlow;
f[node][fat[node]] -= minFlow;
node = fat[node];
}
edgeCount++;
}
}
void PrintEdges()
{
out << edgeCount << "\n";
for (int i = 1; i <= n; ++i)
if (c[0][i])
for (int j = 1; j <= n; ++j)
if (f[i][alt(j)])
out << i << " " << j << "\n";
}
int main()
{
Read();
SetPossibleEdges();
GetMaxFlow();
PrintEdges();
return 0;
}