Pagini recente » Cod sursa (job #1595154) | Cod sursa (job #1159858) | Cod sursa (job #707904) | Cod sursa (job #2202295) | Cod sursa (job #1874505)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");
const int NMAX = 256;
int n, s, src, snk;
vector<int> g[NMAX];
int cap[NMAX][NMAX],
flx[NMAX][NMAX],
gws[NMAX],
far[NMAX],
in[NMAX],
ut[NMAX];
inline int in_nod(const int &nod) { return 2 * nod; }
inline int ut_nod(const int &nod) { return 2 * nod + 1; }
void make_net() {
src = 0;
snk = 1;
for (int i = 1; i <= n; ++i) {
g[src].push_back(ut_nod(i)), g[ut_nod(i)].push_back(src), cap[src][ut_nod(i)] = ut[i];
g[snk].push_back(in_nod(i)), g[in_nod(i)].push_back(snk), cap[in_nod(i)][snk] = in[i];
for (int j = 1; j <= n; ++j) if (i != j) {
g[ut_nod(i)].push_back(in_nod(j));
g[in_nod(j)].push_back(ut_nod(i));
cap[ut_nod(i)][in_nod(j)] = 1; } } }
void pump() {
deque<int> q;
int u, aug;
while (true) {
static int it = 0; ++it;
q.push_back(src);
gws[src] = it;
while (!q.empty()) {
u = q.front();
q.pop_front();
for (auto v: g[u]) if (gws[v] != it && cap[u][v] - flx[u][v] > 0) {
q.push_back(v);
gws[v] = it;
far[v] = u; } }
if (gws[snk] < it)
break;
for (auto lnk: g[snk]) {
aug = cap[lnk][snk] - flx[lnk][snk];
for (int nod = lnk; nod != src; nod = far[nod])
aug = min(aug, cap[far[nod]][nod] - flx[far[nod]][nod]);
for (int nod = lnk; nod != src; nod = far[nod]) {
flx[far[nod]][nod]+= aug;
flx[nod][far[nod]]-= aug; }
flx[lnk][snk]+= aug;
flx[snk][lnk]-= aug; } } }
int main(void) {
int s = 0;
fi >> n;
for (int i = 1; i <= n; ++i) {
fi >> in[i] >> ut[i];
s+= in[i]; }
make_net();
pump();
fo << s << '\n';
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (flx[ut_nod(i)][in_nod(j)])
fo << i << ' ' << j << '\n';
return 0; }