Pagini recente » Cod sursa (job #2686041) | Cod sursa (job #1381076) | Cod sursa (job #542449) | Cod sursa (job #1777703) | Cod sursa (job #1438744)
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,in[206],ies[206],c[206][206],F[206][206],v[206],t[206];
int bfs()
{
int k,u,cd[206];
cd[0]=1;cd[1]=0;
for(int i=1;i<=2*n+1;i++)
v[i]=t[i]=0;
v[0]=1;
for(int j=1;j<=cd[0];j++)
{
k=cd[j];u=2*n+1;
for(int i=1;i<=u;i++)
if(c[k][i]>F[k][i]&& v[i]==0)
{
t[i]=k;v[i]=1;
if(i==u)
return 1;
cd[0]++;cd[cd[0]]=i;
}
}
return v[2*n+1];
}
int main()
{f>>n;
for(int i=1;i<=n;i++)
{f>>ies[i]>>in[i];
c[0][i]=ies[i];
c[n+i][2*n+1]=in[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
c[i][n+j]=1;
int u,z,k;
t[0]=-1;
while(bfs())
{
z=2*n+1;k=10000000;
while(z)
{
if(k>c[t[z]][z]-F[t[z]][z])
k=c[t[z]][z]-F[t[z]][z];
z=t[z];
}
z=2*n+1;
while(z)
F[z][t[z]]= F[z][t[z]]-k,F[t[z]][z]=F[t[z]][z]+k,z=t[z];
}
int nr=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(F[i][j+n]==1)
nr++;
g<<nr<<'\n';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(F[i][j+n]==1)
g<<i<<" "<<j<<'\n';
return 0;
}