Pagini recente » Cod sursa (job #358478) | Cod sursa (job #256802) | Cod sursa (job #2944396) | Cod sursa (job #564430) | Cod sursa (job #13269)
Cod sursa(job #13269)
#include <cstdio>
#include <vector>
using namespace std;
#define Nmax 256
#define pb push_back
#define sz(a) int((a).size())
int n, i, j, s, d, flux, ct;
int grin[Nmax], grout[Nmax], cap[Nmax][Nmax], c[Nmax], tata[Nmax], v[Nmax];
vector<int> lv[Nmax];
void citire()
{
scanf("%d\n", &n);
for (i=1; i<=n; ++i)
scanf("%d %d\n", &grin[i], &grout[i]);
}
int bf()
{
int st = 0, dr = 1, nod, i;
memset(tata, -1, sizeof(tata));
memset(v, 0, sizeof(v));
c[dr] = s;
while (st < dr)
{
nod = c[++st];
for (i=0; i<sz(lv[nod]); ++i)
if (!v[lv[nod][i]] && cap[nod][lv[nod][i]] > 0)
{
v[lv[nod][i]] = 1;
tata[lv[nod][i]] = nod;
c[++dr] = lv[nod][i];
if (lv[nod][i] == d)
return 1;
}
}
return 0;
}
void solve()
{
int nod;
//construiesc graful
s = 0;
d = 2 * n + 1;
for (i=1; i<=n; ++i)
{
cap[s][i] = grin[i];
lv[s].pb(i);
cap[n+i][d] = grout[i];
lv[n+i].pb(d);
}
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (i != j)
{
cap[i][n+j] = 1;
lv[i].pb(n+j);
lv[n+j].pb(i);
}
//fac flux
while (bf())
{
for (i=n+1; i<=2*n; ++i)
if (tata[i] != -1 && cap[i][d] > 0)
{
flux = cap[i][d];
for (nod = i; nod != s; nod = tata[nod])
flux = min(flux, cap[tata[nod]][nod]);
ct += flux;
cap[i][d] -= flux;
cap[d][i] += flux;
for (nod = i; nod != s; nod = tata[nod])
{
cap[tata[nod]][nod] -= flux;
cap[nod][tata[nod]] += flux;
}
}
}
printf("%d\n", ct);
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (i != j && !cap[i][n+j])
printf("%d %d\n",i, j);
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
citire();
solve();
return 0;
}