Pagini recente » Cod sursa (job #9612) | Cod sursa (job #1149466) | Cod sursa (job #758709) | Cod sursa (job #334891) | Cod sursa (job #3190864)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 205;
int N, c[NMAX][NMAX], f[NMAX][NMAX], pr[NMAX], viz[NMAX], M;
vector<int> v[NMAX], sol[NMAX];
void citire()
{
fin >> N;
int x, y;
for (int i = 1; i <= N; i++)
{
fin >> x >> y;
// nodul 0 este sursa, iar nodul 2*N+1 este destinatia
// capacitatiile
c[0][i] += x;
c[N + i][2 * N + 1] += y;
// vecinii
v[0].push_back(i);
v[i].push_back(0);
v[N + i].push_back(2 * N + 1);
v[2 * N + 1].push_back(N + i);
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (i != j)
{
c[i][N + j] += 1;
v[i].push_back(N + j);
v[N + j].push_back(i);
}
fin.close();
}
void reset()
{
for (int i = 0; i <= 2 * N + 1; i++)
viz[i] = 0;
}
int bfs()
{
reset();
viz[0] = 1;
queue<int> Q;
Q.push(0);
while (!Q.empty())
{
int prElem = Q.front();
Q.pop();
for (int i = 0; i < v[prElem].size(); i++)
{
int now = v[prElem][i];
// daca nu este vizitat si nu este saturat
if (viz[now] || c[prElem][now] == f[prElem][now])
continue;
viz[now] = 1;
// retin parintele
pr[now] = prElem;
Q.push(now);
}
}
// return daca am ajuns la destinatie
return viz[2 * N + 1];
}
void max_flow()
{
// cat timp exista drum de la sursa la destinatie
while (bfs())
{
// parcurg drumul de la destinatie la sursa
for (int i = 0; i < v[2 * N + 1].size(); i++)
{
// daca nu este vizitat si nu este saturat
if (!viz[v[2 * N + 1][i]] || c[v[2 * N + 1][i]][2 * N + 1] == f[v[2 * N + 1][i]][2 * N + 1])
continue;
// retin parintele
pr[2 * N + 1] = v[2 * N + 1][i];
int minim = 1 << 30;
// calculez fluxul minim
for (int act = 2 * N + 1; act != 0; act = pr[act])
minim = min(minim, c[pr[act]][act] - f[pr[act]][act]);
// actualizez fluxurile
for (int act = 2 * N + 1; act != 0; act = pr[act])
{
f[pr[act]][act] += minim;
f[act][pr[act]] -= minim;
}
}
}
// construiesc solutia
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (i != j && f[i][N + j])
sol[i].push_back(j), ++M;
}
void write()
{
fout << M << "\n";
for (int i = 1; i <= N; i++)
for (int j = 0; j < sol[i].size(); j++)
fout << i << " " << sol[i][j] << "\n";
fout.close();
}
int main()
{
citire();
max_flow();
write();
return 0;
}