Pagini recente » Cod sursa (job #2109737) | Cod sursa (job #1971725) | Cod sursa (job #2277329) | Cod sursa (job #1241835) | Cod sursa (job #418981)
Cod sursa(job #418981)
#include<cstdio>
#include<bitset>
#include<queue>
#include<vector>
using namespace std;
#define minn(a,b) ((a<b)?a:b)
#define pb push_back
#define NM 205
#define sh short int
#define OO (1<<30)
vector<sh>a[NM];
bitset<NM>viz;
sh N,c[NM][NM],f[NM][NM],x,y,t[NM],u,nod;
queue<sh>q;
int r,flux;
bool bf()
{
viz.reset();
sh S=(N<<1)+2,D=(N<<1)+3;
viz[S]=1;
q.push(S);
++u;
while (u)
{
x=q.front();
q.pop();
--u;
if (x==(N<<1)+3)
continue;
size_t g=a[x].size();
for (size_t i=0; i<g; ++i)
{
y=a[x][i];
if (viz[y]||c[x][y]==f[x][y])
continue;
t[y]=x;
q.push(y);
viz[y]=1;
++u;
}
}
return viz[D];
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%hd",&N);
sh i,j;sh S=(N<<1)+2,D=(N<<1)+3;
for (i=1; i<=N; ++i)
{
for (j=i-1; j; --j)
{
a[i].pb(j+N);
a[j+N].pb(i);
c[i][j+N]=1;
}
for (j=i+1; j<=N; ++j)
{
a[i].pb(j+N);
a[j+N].pb(i);
c[i][j+N]=1;
}
a[S].pb(i);
a[i].pb(S);
a[D].pb(i+N);
a[i+N].pb(D);
scanf("%d%d",&x,&y);
c[S][i]=x;
c[i+N][D]=y;
}
flux=0;
while (bf())
{
size_t g=a[D].size();
for (size_t i=0; i<g; ++i)
{
nod=a[D][i];
if (!viz[nod]||c[nod][D]==f[nod][D])
continue;
t[D]=nod;
r=OO;
for (j=D; j!=S; j=t[j])
r=minn(r,c[t[j]][j]-f[t[j]][j]);
if (!r)
continue;
for (j=D; j!=S; j=t[j])
{
f[t[j]][j]+=r;
f[j][t[j]]-=r;
}
flux+=r;
}
}
int num=0;
for (i=1; i<=N; ++i)
for (j=N+1; j<=(N<<1); ++j)
if (f[i][j]==1)
++num;
printf("%d\n",num);
for (i=1; i<=N; ++i)
for (j=N+1; j<=(N<<1); ++j)
if (f[i][j]==1)
printf("%hd %hd\n",i,j-N);
return 0;
}