Pagini recente » Cod sursa (job #2272868) | Cod sursa (job #1059964) | Cod sursa (job #1425044) | Cod sursa (job #3000764) | Cod sursa (job #941138)
Cod sursa(job #941138)
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
int N, source, sink, M;
vector <int> muchii[211];
int viz[211];
int TT[211];
int cd[211];
int C[211][211];
int F[211][211];
void Citire ()
{
ifstream fin ("harta.in");
fin >> N;
sink = (N << 1) + 1;
for (int i = 1, a, b; i <= N; i++)
{
fin >> a >> b;
C[source][i] = b;
C[i + N][sink] = a;
M += a + b;
}
fin.close ();
}
void Make_Graph ()
{
for (int i = 1; i <= N; i++)
{
muchii[i].pb (source);
muchii[source].pb (i);
muchii[i + N].pb (sink);
muchii[sink].pb (i + N);
for (int j = 1; j < i; j++)
{
muchii[j].pb (i + N);
muchii[i + N].pb (j);
C[j][i + N] = 1;
}
for (int j = i + 1; j <= N; j++)
{
muchii[j].pb (i + N);
muchii[i + N].pb (j);
C[j][i + N] = 1;
}
}
}
int BFS ()
{
cd[cd[0] = 1] = source;
memset (viz, 0, sizeof (viz));
viz[source] = 1;
for (int i = 1; i <= cd[0]; i++)
{
int nod = cd[i];
for (int j = 0; j < muchii[nod].size (); j++)
{
int V = muchii[nod][j];
if (C[nod][V] == F[nod][V] || viz[V]) continue;
viz[V] = 1;
cd[++cd[0]] = V;
TT[V] = nod;
if (V == sink) return 1;
}
}
return 0;
}
void Find_Flow ()
{
while (BFS ())
{
int fmin = 2000000000;
for (int nod = sink; nod != source; nod = TT[nod])
fmin = min (fmin, C[TT[nod]][nod] - F[TT[nod]][nod]);
for (int nod = sink; nod != source; nod = TT[nod])
{
F[TT[nod]][nod] += fmin;
F[nod][TT[nod]] -= fmin;
}
}
}
void Scriere ()
{
ofstream fout ("harta.out");
fout << (M >> 1) << "\n";
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (F[i][j + N]) fout << j << " " << i << "\n";
fout.close ();
}
int main ()
{
Citire ();
Make_Graph ();
Find_Flow ();
Scriere ();
return 0;
}