Pagini recente » Cod sursa (job #2375162) | Cod sursa (job #2748252) | Cod sursa (job #1377904) | Cod sursa (job #812867) | Cod sursa (job #1674825)
#include<bits/stdc++.h>
using namespace std;
typedef struct lnod {
int info;
lnod *next;
}*nod;
const int INF=0x3f3f3f3f;
int i,j,n,x,y,rs,a[205][205],t[205],q[205],st,dr;
bool viz[205];
nod lda[205];
void add(int x,nod &y) {
nod p=new lnod;
p->info=x;
p->next=y;
y=p;
}
void update() {
int nod,flow=INF;
for(nod=n+n+1;nod;nod=t[nod])
flow=min(flow,a[t[nod]][nod]);
rs+=flow;
for(nod=n+n+1;nod!=0;nod=t[nod])
a[t[nod]][nod]-=flow,a[nod][t[nod]]+=flow;
}
bool bfs() {
bool u=0;
memset(viz,0,sizeof(viz));
q[1]=0; viz[0]=1; t[0]=0;
for(st=dr=1;st<=dr;++st)
for(nod p=lda[q[st]];p;p=p->next)
if(a[q[st]][p->info] && !viz[p->info])
{
viz[p->info]=1; t[p->info]=q[st]; q[++dr]=p->info;
if(p->info==n+n+1) update(),viz[n+n+1]=0,--dr,u=1;
}
return u;
}
int main()
{
ifstream cin("harta.in");
ofstream cout("harta.out");
cin>>n;
for(i=1;i<=n;++i)
{
cin>>x>>y;
add(i,lda[0]); a[0][i]=x;
add(0,lda[i]);
add(n+i,lda[n+n+1]);
add(n+n+1,lda[i+n]); a[n+i][n+n+1]=y;
}
for(i=1;i<=n;++i)
for(j=n+1;j<=n+n;++j)
if(i!=j-n) add(j,lda[i]),a[i][j]=1,add(i,lda[j]);
while(bfs());
cout<<rs<<'\n';
for(i=1;i<=n;++i)
for(j=n+1;j<=n+n;++j)
if(a[j][i]) cout<<i<<' '<<j-n<<'\n';
return 0;
}