Pagini recente » Cod sursa (job #2420304) | Cod sursa (job #512665) | Cod sursa (job #883093) | Cod sursa (job #2381055) | Cod sursa (job #480579)
Cod sursa(job #480579)
#include <stdio.h>
#include <vector>
#include <queue>
#define Nmax 105*2
#define INF 2147000000
#define pb push_back
using namespace std;
queue< int > Q;
vector< int > v[Nmax];
int F[Nmax][Nmax],C[Nmax][Nmax];
int prev[Nmax], use[Nmax];
int n,S,D;
inline int Minim(int x,int y){ return x<y ? x:y; }
int bf(){
int x;
vector< int >::iterator it;
memset(use,0,sizeof(use));
Q.push(S); use[S]=1;
while( ! Q.empty() ){
x=Q.front(); Q.pop();
for(it=v[x].begin(); it!=v[x].end(); ++it)
if( F[x][*it] < C[x][*it] && !use[*it] ){
use[*it]=1;
prev[*it]=x;
Q.push(*it);
}
}
return use[D];
}
void flux(){
vector< int >::iterator it;
int fmin,wh;
while( bf() )
for(it=v[D].begin(); it!=v[D].end(); ++it)
if( use[*it] ){
prev[D]=*it; fmin=INF;
for( wh=D; wh!=S && fmin; wh=prev[wh] )
fmin=Minim(fmin,C[prev[wh]][wh]-F[prev[wh]][wh]);
if( fmin == 0 ) continue;
for( wh=D; wh!=S; wh=prev[wh] ){
F[prev[wh]][wh] += fmin;
F[wh][prev[wh]] -= fmin;
}
}
}
int main(){
int i,j,x,y,m=0;
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
D=2*n+1; S=2*n+2;
for(i=1;i<=n;++i){
scanf("%d%d",&x,&y);
m += x;
v[S].pb(i); v[i].pb(S); C[S][i]=x;
v[i+n].pb(D); v[D].pb(i+n); C[i+n][D]=y;
for(j=1;j<=n;++j)
if(i!=j){
v[i].pb(j+n); v[j+n].pb(i);
C[i][j+n]=1;
}
}
flux();
printf("%d\n",m);
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
if( F[i][j] ) printf("%d %d\n",i,j-n);
fclose(stdin); fclose(stdout);
return 0;
}