Pagini recente » Monitorul de evaluare | Cod sursa (job #1206739) | Profil M@2Te4i | Istoria paginii template/monthly-2012 | Cod sursa (job #221269)
Cod sursa(job #221269)
#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;
void print(){
int i,j;
for (i=0;i<=2*n+1;++i){
for (j=0;j<=2*n+1;++j)
printf("%d ",flux[i][j]);
printf("\n");
}
printf("\n");
for (i=0;i<=2*n+1;++i){
for (j=0;j<=2*n+1;++j)
printf("%d ",c[i][j]);
printf("\n");
}
printf("\n");
}
bool bf(){
int i;
queue<int> Q;//fprintf(stderr,"\n");
Q.push(0);//printf("%s ","am intrat in bf");
//t.resize(2*n+2,-1);
//print();
for (i=0;i<=2*n+1;++i)
t[i]=-1;
//for (i=0;i<=2*n+1;++i)
//printf("%d ",t[i]);
while (!Q.empty()){
//fprintf(stderr,"%d\n",Q.front());
for(i=1;i<=2*n+1;++i)
if (flux[Q.front()][i]<c[Q.front()][i] && t[i]==-1){
Q.push(i);
t[i]=Q.front();
if(i==2*n+1)
return true;
}
Q.pop();
}
return false;
}
int minim(){
int i=2*n+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=2*n+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(2*n+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<=2*n;++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<=2*n;++i)
c[i][2*n+1]=in[i-n];
fluxx();
for (i=1;i<=n;++i)
for (j=n+1;j<=2*n;++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);
}