Cod sursa(job #534460)
#include <fstream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#include <vector>
#include <queue>
#define oo 200000000
#define maxn 256
#define pb push_back
int i,j,N,s,d,k,R,flmin;
int C[maxn][maxn],from[maxn],v[maxn];
vector <short> A[maxn];
queue <short> Q;
inline int min(int a, int b)
{
return a<b ? a : b;
}
void citire()
{
int x,y;
fin >> N;
s=0; d=2*N+1;
for(i=1;i<=N;i++)
{
fin >> x >> y;
A[s].pb(i); C[s][i]=x;
A[i+N].pb(d); C[i+N][d]=y;
for(j=N+1;j<d;j++)
if(j!=i+N)
{
A[i].pb(j);
A[j].pb(i);
C[i][j]=1;
}
}
}
int BFS()
{
for(i=1;i<=d;i++) v[i]=0;
for(;!Q.empty();Q.pop());
Q.push(s); v[s]=1;
for(;!Q.empty();Q.pop())
{
k=Q.front();
for(i=0;i<(int)A[k].size();i++)
if(C[k][A[k][i]]>0 && !v[A[k][i]])
{
from[A[k][i]]=k;
if(A[k][i]==d) return 1;
Q.push(A[k][i]);
v[A[k][i]]=1;
}
}
return 0;
}
int main()
{
citire();
while( BFS() )
{
flmin=oo;
for(k=d;k!=s;k=from[k])
flmin=min(flmin,C[from[k]][k]);
for(k=d;k!=s;k=from[k])
{
C[from[k]][k]-=flmin;
C[k][from[k]]+=flmin;
}
R+=flmin;
}
fout << R << '\n';
for(i=1;i<=N;i++)
for(j=0;j<(int)A[i].size();j++)
if(C[i][A[i][j]]==0 && A[i][j]>N)
fout << i << ' ' << A[i][j]-N << '\n';
}