Pagini recente » Cod sursa (job #16247) | Cod sursa (job #1174649) | Cod sursa (job #2538189) | Cod sursa (job #927259) | Cod sursa (job #433324)
Cod sursa(job #433324)
#include<fstream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m,S,T,flow;
int c[202][202],f[202][202],di[101],de[101],x[202],t[202],pus[202];
void augment()
{ int j=T,i;
while(j!=S)
{ i=abs(t[j]);
if(t[j]>=0) f[i][j]++;
else f[j][i]--;
j=i;
}
flow++;
}
int bf()
{ int st=1,dr=1,i;
for(i=1;i<=T;i++)
{ t[i]=0;
pus[i]=0;
x[i]=0;
}
x[1]=S;
pus[S]=1;
while(st<=dr)
{ int nod=x[st];
for(i=1;i<=T;i++)
if(pus[i]==0)
{ if(c[nod][i]>f[nod][i])
{ x[++dr]=i;
pus[i]=1;
t[i]=nod;
if(i==T) return 1;
}
if(f[i][nod])
{ x[++dr]=i;
pus[i]=1;
t[i]=-nod;
if(i==T) return 1;
}
}
st++;
}
return 0;
}
void flux()
{ while(bf())
augment();
}
int main()
{ int i,j;
fin>>n;
for(i=1;i<=n;i++)
fin>>de[i]>>di[i];
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(i!=j-n) c[i][j]=1;
S=0;
T=2*n+1;
for(i=1;i<=n;i++)
{ c[0][i]=de[i];
c[i+n][T]=di[i];
}
flux();
fout<<flow<<"\n";
for(i=1;i<=n;i++)
for(j=n+1;j<=T;j++)
if(f[i][j]) fout<<i<<" "<<j-n<<"\n";
fin.close();
fout.close();
return 0;
}