Pagini recente » Cod sursa (job #1254882) | Cod sursa (job #2427692) | Istoria paginii runda/meister/clasament | Cod sursa (job #2662182) | Cod sursa (job #396603)
Cod sursa(job #396603)
#include <algorithm>
#include <queue>
using namespace std;
#define DIM 205
int c[DIM][DIM],f[DIM][DIM];
int n,s,d,flow;
queue <int> q;
int t[DIM];
void read ()
{
int i,j,x,y;
scanf ("%d",&n);
s=0; d=2*n+1;
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (i!=j)
c[i][j+n]=1;
for (i=1; i<=n; ++i)
{
scanf ("%d%d",&x,&y);
c[s][i]=x;
c[i+n][d]=y;
}
}
int bf ()
{
int nod,i;
memset (t,-1,sizeof (t));
for (q.push (s); !q.empty (); q.pop ())
{
nod=q.front ();
for (i=s; i<=d; ++i)
if (t[i]==-1 && c[nod][i]-f[nod][i]>0)
{
t[i]=nod;
q.push (i);
}
}
return t[d];
}
void solve ()
{
int i,j,minim;
for ( ; bf ()!=-1; )
for (i=s; i<=d; ++i)
if (t[i]>=0 && c[i][d]-f[i][d]>0)
{
minim=c[i][d]-f[i][d];
for (j=i; j!=s; j=t[j])
minim=min (minim,c[t[j]][j]-f[t[j]][j]);
f[i][d]+=minim;
f[d][i]-=minim;
for (j=i; j!=s; j=t[j])
{
f[t[j]][j]+=minim;
f[j][t[j]]-=minim;
}
flow+=minim;
}
}
void print ()
{
int i,j;
printf ("%d\n",flow);
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (f[i][j+n])
printf ("%d %d\n",i,j);
}
int main ()
{
freopen ("harta.in","r",stdin);
freopen ("harta.out","w",stdout);
read ();
solve ();
print ();
return 0;
}