Pagini recente » Cod sursa (job #3228728) | Cod sursa (job #1672151) | Cod sursa (job #2298184) | Cod sursa (job #894804) | Cod sursa (job #580872)
Cod sursa(job #580872)
#include<cstdio>
#include<queue>
#define Nmax 128
#define Cmax 256
#define inf 0x3f3f3f3f
#define dr(x) (N+x)
#define st(x) (x-N)
using namespace std;
int N,cp[Cmax][Cmax],fm[Cmax][Cmax],D,t[Cmax];
bool viz[Cmax];
int bf(){
queue <int> c;
memset(viz,0,sizeof(viz));
c.push(0);
viz[0]=1;
while(!c.empty()){
int nod=c.front();
c.pop();
for(int i=0;i<=D;++i){
if(!viz[i] && cp[nod][i] > fm[nod][i]){
if(i==D)
return 1;
t[i]=nod;
viz[i]=1;
c.push(i);
}
}
}
return 0;
}
int main(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&N);
D=2*N+1;
for(int i=1;i<=N;++i){
int x,y;
scanf("%d%d",&x,&y);
cp[0][i]=x; //din nodul i pleaca x muchii
cp[dr(i)][D]=y; //in nodul i intra x muchii
for(int j=1;j<=N;++j)
if(i!=j)
cp[i][dr(j)]=1; //adaugam muchii de cap 1 intre nodurile distincte
}
//calculam flux
int flux=0;
while(bf()){
for(int i=N+1;i<D;++i)
if(cp[i][D]>fm[i][D]){
t[D]=i;
int fmn=inf;
for(int nod=D;nod!=0;nod=t[nod])
fmn=min(fmn,cp[t[nod]][nod]-fm[t[nod]][nod]);
for(int nod=D;nod!=0;nod=t[nod]){
fm[t[nod]][nod]+=fmn;
fm[nod][t[nod]]-=fmn;
}
flux+=fmn;
}
}
printf("%d\n",flux);
for(int i=1;i<=N;++i)
for(int j=N+1;j<=2*N;++j)
if(fm[i][j])
printf("%d %d\n",i,st(j));
return 0;
}