Pagini recente » Cod sursa (job #2364670) | Cod sursa (job #601813) | Cod sursa (job #2200698) | Cod sursa (job #251672) | Cod sursa (job #320042)
Cod sursa(job #320042)
#include <stdio.h>
using namespace std;
#define maxn 1010
long n, i, m, j, k, a, b, x, l, r, pl, ss, ok, nod, sol, nd, c[maxn][maxn], up[maxn], f[maxn], coa[maxn];
long min(long a, long b)
{
if(a>b) return b;
return a;
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d %d", &pl, &ss);
nd+=pl;
c[1][i+1]=pl;
c[i+n+1][2*n+2]=ss;
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(i!=j) c[i+1][j+n+1]=1;
}
}
n=n*2+2;
ok=1;
while(ok)
{
for(i=1; i<=n; i++)
{
f[i]=0;
up[i]=-1;
}
f[1]=111100;
coa[1]=1;
for(l=1, r=1; l<=r; l++)
{
nod=coa[l];
for(i=1; i<=n; i++)
{
if(f[i]==0 && c[nod][i]>0)
{
f[i]=min(f[nod], c[nod][i]);
up[i]=nod;
r++;
coa[r]=i;
}
}
if(f[n]>0) break;
}
nod=n;
if(f[n]>0)
{
ok=1;
sol+=f[n];
while(up[nod]!=-1)
{
i=up[nod];
c[nod][i]+=f[n];
c[i][nod]-=f[n];
nod=up[nod];
}
}
else ok=0;
}
n=n/2-1;
printf("%d\n", nd);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(i!=j && c[i+1][n+j+1]==0) printf("%d %d\n", i, j);
}
}
return 0;
}