Pagini recente » Cod sursa (job #2117658) | Cod sursa (job #563661) | Cod sursa (job #76301) | Cod sursa (job #483055) | Cod sursa (job #219796)
Cod sursa(job #219796)
#include<stdio.h>
#include<string.h>
#define N 205
int n,s,d,m;
int c[N][N],f[N][N],t[N],flux;
void citire()
{
int x,y,j;
for(int i=1; i<=n; i++)
{
scanf("%d%d",&x,&y);
c[0][i]=x;
c[i+n][d]=y;
m+=x;
for(j=1; j<=n; j++)
{
if(j==i)
continue;
c[i][j+n]=1;
}
}
}
bool bfs()
{
int p,u,nod,i,q[N];
memset(t,0xff,sizeof(t));
p=u=0;
q[0]=s;
t[s]=-1;
for(; p<=u; p++)
{
nod=q[p];
for(i=0; i<=d; i++)
{
if(t[i]==-1 && c[nod][i]>f[nod][i])
{
q[++u]=i;
t[i]=nod;
if(i==d)
return true;
}
}
}
return false;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
d=(n<<1)+1;
citire();
int i,j;
while(bfs())
{
i=d;
while(i)
{
f[t[i]][i]++;
f[i][t[i]]--;
i=t[i];
}
}
printf("%d\n",m);
for(i=1; i<=n; i++)
{
for(j=n+1; j<d; j++)
{
if(f[i][j]>0)
printf("%d %d\n",i,j-n);
}
}
return 0;
}