Pagini recente » Cod sursa (job #2741476) | Cod sursa (job #2825263) | Cod sursa (job #2464416) | Cod sursa (job #967720) | Cod sursa (job #2628414)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
const int inf=2e9+7;
vector<int> vec[205];
int in[105],out[205];
int c[205][205];
int pred[205];
queue<int> q;
int main()
{
int n,si=0,so=0;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>out[i]>>in[i];
so+=out[i];
si+=in[i];
}
if(so!=si)
{
cout<<-1<<'\n';
return 0;
}
for(int i=1;i<=n;++i)
{
/*vec[i].push_back(i+n);
vec[i+n].push_back(i);
c[i+n][i]=inf;*/
vec[0].push_back(i);
vec[i].push_back(0);
c[0][i]=out[i];
vec[i+n].push_back(2*n+1);
vec[2*n+1].push_back(i+n);
c[i+n][2*n+1]=in[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j)
{
vec[i].push_back(j+n);
vec[j+n].push_back(i);
c[i][j+n]=1;
}
int flow=0,ads;
do
{
for(int i=1;i<=2*n+1;++i)
pred[i]=-1;
pred[0]=-2;
q.push(0);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int y:vec[x])
if(pred[y]==-1 and c[x][y]>0)
{
pred[y]=x;
q.push(y);
}
}
if(pred[2*n+1]>=0)
for(int t=n+1;t<=2*n;++t)
if(pred[t]>=0 and c[t][2*n+1]>0)
{
ads=c[t][2*n+1];
for(int k=t;pred[k]>=0;k=pred[k])
ads=min(ads,c[pred[k]][k]);
if(ads<=0) continue;
c[t][2*n+1]-=ads;
c[2*n+1][t]+=ads;
for(int k=t;pred[k]>=0;k=pred[k])
{
c[pred[k]][k]-=ads;
c[k][pred[k]]+=ads;
}
flow+=ads;
}
}while(pred[2*n+1]>=0);
if(flow!=si)
{
cout<<-1<<'\n';
return 0;
}
cout<<flow<<'\n';
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j and c[i][j+n]==0)
cout<<i<<' '<<j<<'\n';
return 0;
}