Cod sursa(job #884834)
#include <fstream>
#include <vector>
#include <list>
#define nmax 203
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> vec[nmax];
list <int> coada;
int n,d,viz[nmax],flux[nmax][nmax],tata[nmax];
int bfs()
{
int i,j,nod;
for(i=1;i<=d;i++) viz[i]=0;
viz[1]=1;
coada.push_back(1);
while(!coada.empty())
{
nod=coada.front();
for(i=0;i<vec[nod].size();i++)
{
j=vec[nod][i];
if(j==n && flux[nod][d]) {viz[d]=1; continue;}
if(viz[j] || !flux[nod][j]) continue;
viz[j]=1; tata[j]=nod;
coada.push_back(j);
}
coada.pop_front();
}
return viz[d];
}
int main()
{
int x,y,i,j,fmin,fmax=0;
f>>n;
d=2*n+2;
for(i=1;i<=n;i++)
{
f>>x>>y;
vec[1].push_back(i+1);
vec[i+1].push_back(1);
vec[i+n+1].push_back(d);
vec[d].push_back(i+n+1);
flux[1][i+1]=x;
flux[i+n+1][d]=y;
}
for(i=2;i<=n+1;i++)
{
for(j=n+2;j<=2*n+1;j++)
{
if(j-i==n) continue;
vec[i].push_back(j);
vec[j].push_back(i);
flux[i][j]=1;
}
}
int nod;
while(bfs())
{
for(j=0;j<vec[d].size();j++)
{
nod=vec[d][j];
tata[d]=nod;
fmin=100000;
for(i=d;i!=1;i=tata[i])
{
if(flux[tata[i]][i]<fmin) fmin=flux[tata[i]][i];
}
if(!fmin) continue;
for(i=d;i!=1;i=tata[i])
{
flux[tata[i]][i]-=fmin;
flux[i][tata[i]]+=fmin;
}
fmax+=fmin;
}
}
g<<fmax<<'\n';
for(i=n+2;i<=2*n+1;i++)
{
for(j=2;j<=n+1;j++)
{
if(flux[i][j]) g<<j-1<<' '<<i-n-1<<'\n';
}
}
}