Pagini recente » Cod sursa (job #1646149) | Cod sursa (job #485670) | Cod sursa (job #1258912) | Cod sursa (job #1546994) | Cod sursa (job #1212661)
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
vector <int> v[105];
queue <int> q;
bitset <210> viz;
int n,m,p,x,y,T[210],C[210][210],F[210][210];
int bfs()
{
int i;
viz.reset();
for (i=0;i<=2*n+1;++i)
T[i]=-1;
viz[0]=1; q.push(0);
while (!q.empty())
{
x=q.front(); q.pop();
for (i=0;i<v[x].size();++i)
{
y=v[x][i];
if (!viz[y] && C[x][y]>F[x][y])
{
viz[y]=1, T[y]=x;
q.push(y);
}
}
}
return viz[2*n+1];
}
int main()
{
int i,j;
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
v[0].push_back(i); v[i].push_back(0);
v[i+n].push_back(2*n+1); v[2*n+1].push_back(i+n);
C[0][i]=x;
C[i+n][2*n+1]=y;
}
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (i!=j)
{
v[i].push_back(j+n), v[j+n].push_back(i);
C[i][j+n]=1;
}
while (bfs())
for (i=0;i<v[2*n+1].size();++i)
{
x=v[2*n+1][i];
if (viz[x] && C[x][2*n+1]>F[x][2*n+1])
{
p=C[x][2*n+1]-F[x][2*n+1];
while (!(T[x]<0))
{
p=min(p,C[T[x]][x]-F[T[x]][x]);
x=T[x];
}
m+=p;
x=v[2*n+1][i];
F[x][2*n+1]+=p, F[2*n+1][x]-=p;
while (!(T[x]<0))
{
F[T[x]][x]+=p, F[x][T[x]]-=p;
x=T[x];
}
}
}
printf("%d\n",m);
for (i=1;i<=n;++i)
for (j=1;j<=m;++j)
if (F[i][j+n]==1)
printf("%d %d\n",i,j);
return 0;
}