Pagini recente » Cod sursa (job #943166) | Cod sursa (job #1186471) | Cod sursa (job #3281074) | Cod sursa (job #1301234) | Cod sursa (job #1854013)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
struct celula{
int nod;
celula *next;
}*g[1001],*a;
int n,m,x,y,cost,i,flow,j;
int c[1001][1001];
int t[1001],q[1001];
bool viz[1001];
void update()
{
int mini=2000000000;
int aux=2*n+1;
while(aux>1)
{
mini=min(mini,c[t[aux]][aux]);
aux=t[aux];
}
flow+=mini;
aux=2*n+1;
while(aux>1)
{
c[t[aux]][aux]-=mini;
c[aux][t[aux]]+=mini;
aux=t[aux];
}
}
bool bfs()
{
q[1]=0;
int l=1, r=1;
int nod=1;
int ok=0;
memset(viz,0,sizeof(viz));
viz[0]=1;
while(l<=r)
{
nod=q[l];
l++;
for(celula *p=g[nod]; p!=NULL; p=p->next)
{
if(viz[p->nod]==0 && c[nod][p->nod]>0)
{
t[p->nod]=nod;
if(p->nod==2*n+1) update(), ok=1;
else
q[++r]=p->nod, viz[p->nod]=1;
}
}
}
return ok;
}
int main()
{
cin>>n;
for(i=1;i<=n;++i)
{
cin>>x>>y;
a = new celula;
a->nod=i;
a->next=g[0];
g[0]=a;
c[0][i]=x;
a= new celula;
a->nod=0;
a->next=g[i];
g[i]=a;
c[i][0]=0;
a= new celula;
a->nod=2*n+1;
a->next=g[n+i];
g[n+i]=a;
c[n+i][2*n+1]=y;
a=new celula;
a->nod=n+i;
a->next=g[2*n+1];
g[2*n+1]=a;
c[2*n+1][n+i]=0;
}
for(i=1;i<=n;++i)
{
for(j=n+1;j<=2*n;++j)
{
if(j==n+i)
continue;
else
{
a=new celula;
a->nod=i;
a->next=g[j];
g[j]=a;
c[i][j]=1;
a= new celula;
a->nod=j;
a->next=g[i];
g[i]=a;
c[j][i]=0;
}
}
}
while(bfs())
{
}
cout<<flow<<"\n";
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
{
if(j!=n+i)
if(c[i][j]==0) cout<<i<<" " << j-n<<"\n";
}
return 0;
}