Cod sursa(job #761399)
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int N=206;
int c[N][N],f[N][N],pred[N],n;
bool use[N];
vector <int> v[N];
bool bfs()
{
int x;
memset(use,false, sizeof(use));
memset(pred,0, sizeof(pred));
queue<int> q;
q.push(0);
use[0]=true;
pred[0]=-1;
while(!q.empty())
{
x=q.front();
q.pop();
for(vector <int> :: iterator it=v[x].begin(); it!=v[x].end();it++)
{
if(!use[*it] && c[x][*it]-f[x][*it]>0)
{
use[*it]=1;
pred[*it]=x;
q.push(*it);
if(*it==2*n+1)
return true;
}
}
}
return false;
}
int calcmin(int x)
{
int min=c[x][2*n+1]-f[x][2*n+1];
while(pred[x]!=-1)
{
if(c[pred[x]][x]-f[pred[x]][x]<min)
min=c[pred[x]][x]-f[pred[x]][x];
x=pred[x];
}
return min;
}
void flux()
{
int flux,x,mm;
while(bfs())
{
for(vector<int> :: iterator it=v[2*n+1].begin();it!=v[2*n+1].end();it++)
{
if(use[*it] && c[*it][2*n+1]>f[*it][2*n+1])
{
mm=calcmin(*it);
f[*it][2*n+1]+=mm;
f[2*n+1][*it]-=mm;
x=*it;
while(pred[x]!=-1)
{
f[pred[x]][x]+=mm;
f[x][pred[x]]-=mm;
x=pred[x];
}
}
}
}
}
int main()
{
int i,j,x,y,nr=0;
in>>n;
for(i=1;i<=n;i++)
{
in>>x>>y;
v[0].push_back(i);
v[i].push_back(0);
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
c[0][i]=x;
c[n+i][2*n+1]=y;
nr+=x;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
v[i].push_back(n+j);
v[n+j].push_back(i);
c[i][n+j]=1;
}
flux();
out<<nr<<"\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j && f[i][j+n])
out<<i<<" "<<j<<"\n";
return 0;
}