Pagini recente » Cod sursa (job #1118864) | Statistici --- (OutLawer) | Statistici manea adelina (inna) | Monitorul de evaluare | Cod sursa (job #221246)
Cod sursa(job #221246)
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 120
#define oo 19383934
using namespace std;
vector<int> in,out;
queue<int> Q;
int c[2*N][2*N],flux[2*N][2*N];
vector<int> t;
int n;
bool bf(){
int i;
Q.push(0);
t.resize(2*n+1,-1);
while (!Q.empty()){
for(i=1;i<=2*n;++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;
while(i){
if(c[t[i]][i]-flux[t[i]][i]<m)
m=c[t[i]][i]-flux[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;
}
}
void fluxx(){
int i,j,minx=oo;
while (bf()){
minx=minim();
update(minx);
}
}
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)
c[0][i]=out[i];
for (i=n+1;i<=2*n;++i)
c[i][2*n+1]=in[i];
fluxx();
for (i=1;i<=n;++i)
for (j=n+1;j<=2*n;++j);
if (c[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);
}