Pagini recente » Cod sursa (job #191307) | Cod sursa (job #1729265) | Cod sursa (job #181307) | Cod sursa (job #2021615) | Cod sursa (job #2710945)
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
int flow, n, s_in,s_out, g[1010][1010], T[1010], q[1010];
inline void scan();
bool bfs();
int main()
{
scan();
while(bfs())
{
for(int nod=2*n+1; nod!=0; nod=T[nod])
g[T[nod]][nod]--, g[nod][T[nod]]++;
}
if(flow<s_in)
cout<<-1<<'\n';
else{
cout<<flow<<'\n';
for(int i=1; i<=n; ++i)
for(int j=1+n; j<=2*n; ++j)
if(g[j][i])
cout<<i<<' '<<j-n<<'\n';
}
return 0;
}
inline void scan()
{
int x,y;
cin>>n;
for(int i=1; i<=n; ++i)
{
cin>>x>>y;
s_in+=x;
s_out+=y;
g[0][i]=x;
g[i+n][2*n+1]=y;
}
if(s_in!=s_out)
{
cout<<-1<<'\n';
exit(0);
}
for(int i=1; i<=n; ++i)
for(int j=n+1; j<=2*n; ++j)
if(j-i!=n)
g[i][j]=1;
}
bool bfs()
{
for(int i=0; i<=2*n+1; ++i)
T[i]=-1, q[i]=0;
int head=0, tail=0, nod=0;
q[0]=0; T[0]=0;
for(head=tail=0; head<=tail; ++head)
{
nod=q[head];
for(int j=1; j<=2*n+1; ++j)
if(g[nod][j] && T[j]==-1)
{
T[j]=nod;
q[++tail]=j;
if(j==2*n+1)
{
flow++;
return 1;
}
}
}
return 0;
}