Pagini recente » Rating petrea andrei (o_dai_cu_ady_papushika) | Cod sursa (job #257422) | Cod sursa (job #3285547) | Cod sursa (job #1925516) | Cod sursa (job #1276200)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define NN 210
queue< pair<int,int> > qq;
struct node{
int val;
node *next;
};
node *G[NN],*tmp;
int n , m , x , y , z , i ;
int st[NN] , ant[NN],cap[NN][NN],flux[NN][NN];
bool viz[NN];
void add(int x,int y){
tmp = new node;
tmp->val = y;
tmp->next= G[x];
G[x] = tmp;
}
bool bfs(){
st[0] = 1; st[1] = 0;
memset( viz , NULL , sizeof(viz) );
for( i = 1; i <= st[0] ; ++i ){
x = st[i];
if( x == m ) continue;
for( tmp = G[ x]; tmp ; tmp = tmp->next ){
y = tmp->val;
if( cap[x][y] == flux[x][y] || viz[y] ) continue;
viz[y] = true;
ant[y] = x;
st[ ++st[0] ] = y;
}
}
return viz[m];
}
int main()
{
freopen("harta.in" , "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d",&n);
m =2*n + 1;
for(i=1;i<=n;++i){
scanf("%d %d",&x,&y);
add( 0 , i );
add( i , 0 );
cap[0 ][i] = x;
cap[i+n][m] = y;
add(i+n,m);
add(m,i+n);
for(int j=1;j<=n;++j){
if( i == j ) continue;
add(i,j+n);
add(j+n,i);
cap[i][j+n] = 1;
}
//cap[x][y] += z;
}
int flow,fmin;
while( bfs() )
for(tmp=G[m] ; tmp ; tmp = tmp->next ){
x = tmp->val;
if( flux[x][m] == cap[x][m] || !viz[x] ) continue;
ant[m] = x;
fmin = 1 << 30;
for(x=m; x; x= ant[x] )
fmin = min(fmin , cap[ ant[x] ][x] - flux[ ant[x] ][x] );
if( fmin == 0 ) continue;
for(x=m; x; x= ant[x]){
flux[ ant[x] ][x] += fmin;
flux[x][ ant[x] ] -= fmin;
}
//flow += fmin;
}
//printf("%d",flow);
for(i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if( i == j ) continue;
if( flux[i][j+n] == 1 )
qq.push( {i,j} );
}
}
int tt= qq.size();
printf("%d\n",tt);
for( ; tt ; tt-- ){
printf("%d %d\n",qq.front().first,qq.front().second);
qq.pop();
}
return 0;
}