Pagini recente » Cod sursa (job #2275352) | Cod sursa (job #462920) | Cod sursa (job #334845) | Cod sursa (job #1003774) | Cod sursa (job #221270)
Cod sursa(job #221270)
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 120
#define oo 19383934
using namespace std;
vector<int> in,out;
int c[2*N][2*N],flux[2*N][2*N];
vector<int> t;
int n;
bool bf(){
int i;
queue<int> Q;//fprintf(stderr,"\n");
Q.push(0);//printf("%s ","am intrat in bf");
//t.resize((n<<1)+2,-1);
//print();
for (i=0;i<=(n<<1)+1;++i)
t[i]=-1;
//for (i=0;i<=(n<<1)+1;++i)
//printf("%d ",t[i]);
while (!Q.empty()){
//fprintf(stderr,"%d\n",Q.front());
for(i=1;i<=(n<<1)+1;++i)
if (flux[Q.front()][i]<c[Q.front()][i] && t[i]==-1){
Q.push(i);
t[i]=Q.front();
if(i==(n<<1)+1)
return true;
}
Q.pop();
}
return false;
}
int minim(){
int i=n<<1+1,m=oo;
//printf("\n***\n");
while(i){
//printf("j=%d ",i);
if(c[t[i]][i]-flux[t[i]][i]<m)
m=c[t[i]][i]-flux[t[i]][i];
//printf("(%d,%d) ",t[i],i);
i=t[i];
}
return m;
}
void update(int dif){
int i=(n<<1)+1;
while(i){
flux[t[i]][i]+=dif;
flux[i][t[i]]-=dif;
i=t[i];
//printf("i=%d ",i);
}
}
void fluxx(){
int i,j,minx=oo;
while (bf()){
//minx=minim();
update(1);
}
}
vector< pair<int,int> > sol;
main(){
int i,j;
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
in.resize(n+1);
out.resize(n+1);
t.resize((n<<1)+3,-1);
for (i=1;i<=n;++i)
scanf("%d%d",&out[i],&in[i]);
for (i=1;i<=n;++i)
for (j=n+1;j<=(n<<1);++j)
if (j!=i+n)
c[i][j]=1;
for (i=1;i<=n;++i)
c[0][i]=out[i];
for (i=n+1;i<=(n<<1);++i)
c[i][(n<<1)+1]=in[i-n];
fluxx();
for (i=1;i<=n;++i)
for (j=n+1;j<=(n<<1);++j)
if (flux[i][j]==1)
sol.push_back(make_pair(i,j-n));
printf("%d\n",sol.size());
for (i=0;i<sol.size();++i)
printf("%d %d\n",sol[i].first,sol[i].second);
}