Pagini recente » Cod sursa (job #1298088) | Cod sursa (job #458828) | Cod sursa (job #330592) | Cod sursa (job #2456952) | Cod sursa (job #3323175)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
const int DIM = 202, DIMM = 10100;
struct muchie
{
int nod, pos;
};
muchie t[DIM + 1];
vector <muchie> v[DIM + 1];
int n, m, dp[DIM + 1];
queue <int> q;
int sume, pos, c[2 * DIMM + 1], se[DIM / 2], si[DIM / 2];
void add_mch (int l, int r, int p)
{
v[l].push_back ({r, m});
m++;
v[r].push_back ({l, m});
c[m - 1] = p, c[m] = 0;
m++;
}
void read ()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> se[i] >> si[i];
sume += se[i];
add_mch (1, 2 * i, se[i]);
add_mch (2 * i + 1, 2 * n + 2, si[i]);
}
pos = m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
add_mch (2 * i, 2 * j + 1, 1);
}
}
}
bool bfs ()
{
for (int i = 0; i <= 2 * n + 2; i++)
t[i] = {0, 0}, dp[i] = 0;
q.push (1);
dp[1] = sume;
while (!q.empty ())
{
int nod = q.front ();
q.pop ();
for (int i = 0; i < (int) v[nod].size (); i++)
{
int vecin = v[nod][i].nod;
int pos = v[nod][i].pos;
if (dp[vecin] == 0 && c[pos])
{
t[vecin] = {nod, pos};
q.push (vecin);
dp[vecin] = min (c[pos], dp[nod]);
}
}
}
return dp[2 * n + 2];
}
void add_flux (int flux)
{
int nod = 2 * n + 2;
while (nod != 1)
{
c[t[nod].pos] -= flux;
c[t[nod].pos ^ 1] += flux;
nod = t[nod].nod;
}
}
void solve ()
{
int sol = 0;
while (bfs ())
{
int flux = dp[2 * n + 2];
add_flux (flux);
sol += flux;
}
fout << sol << "\n";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
if (c[pos] == 0)
fout << i << " " << j << "\n";
pos += 2;
}
}
}
}
int main ()
{
read ();
solve ();
return 0;
}