Pagini recente » Cod sursa (job #2500809) | Cod sursa (job #1305330) | Cod sursa (job #1159941) | Cod sursa (job #298720) | Cod sursa (job #571912)
Cod sursa(job #571912)
#include<cstdio>
#include<vector>
#include<queue>
#define minim(a, b) ((a)<=(b)?(a):(b))
#define InFile "harta.in"
#define OutFile "harta.out"
using namespace std;
const int MaxN = 1 << 8;
const int INF = 0x3f3f3f3f;
int n,S,D,C[MaxN][MaxN],F[MaxN][MaxN],T[MaxN],viz[MaxN];
vector<int> G[MaxN];
queue<int> Q;
void read_BuildGraph()
{
freopen( InFile , "r" , stdin );
scanf("%d" , &n );
S = 2*n+1;
D = 2*n+2;
int i,j,x,y;
for( i = 1 ; i <= n ; i++ )
{
scanf("%d%d" , &x , &y );
G[S].push_back(i);
G[i].push_back(S);
C[S][i] = x;
G[n+i].push_back(D);
G[D].push_back(n+i);
C[n+i][D] = y;
}
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
if( i != j )
{
G[i].push_back(n+j);
G[n+j].push_back(i);
C[i][n+j] = 1;
}
}
int BFS(int s , int d )
{
memset(viz,0,sizeof(viz));
viz[s] = 1;
Q.push(s);
while( !Q.empty() )
{
int nod;
vector<int>::iterator it;
nod = Q.front();
Q.pop();
if( nod == d )
continue;
for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
if( !viz[*it] && C[nod][*it] > F[nod][*it] )
{
viz[*it] = 1;
T[*it] = nod;
Q.push(*it);
}
}
return viz[d];
}
int flux()
{
int Flux = 0;
while( BFS(S,D) )
{
int minflux,nod;
vector<int>::iterator it;
for( it = G[D].begin() ; it != G[D].end() ; ++it )
if( T[*it] && C[*it][D] > F[*it][D] )
{
T[D] = *it;
minflux = INF;
nod = D;
while( nod != S )
{
minflux = minim(minflux,C[T[nod]][nod] - F[T[nod]][nod] );
nod = T[nod];
}
nod = D;
while( nod != S )
{
F[T[nod]][nod] += minflux;
F[nod][T[nod]] -= minflux;
nod = T[nod];
}
Flux += minflux;
}
}
return Flux;
}
void write()
{
freopen( OutFile , "w" , stdout );
printf("%d\n" , flux());
int i,j;
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
if( i != j && C[i][n+j] == F[i][n+j] )
printf("%d %d\n" , i , j);
}
int main()
{
read_BuildGraph();
write();
return 0;
}