Pagini recente » Cod sursa (job #363308) | Cod sursa (job #2505271) | Cod sursa (job #2696610) | Cod sursa (job #917726) | Cod sursa (job #563132)
Cod sursa(job #563132)
#include<stdio.h>
#define maxN 105
#define Srs (N<<1)+1
#define Dst (N<<1)+2
#include<vector>
using namespace std;
FILE*f=fopen("harta.in","r");
FILE*g=fopen("harta.out","w");
int N,i,j,in,out,C[maxN << 1],Viz[maxN << 1],T[maxN << 1];
int Cp[maxN << 1][maxN << 1],F[maxN << 1][maxN << 1];
vector<int>A[maxN << 1];
void conecteaza(int nod1,int nod2,int c){
A[nod1].push_back(nod2);
A[nod2].push_back(nod1);
Cp[nod1][nod2] = c;
}
int Bfs () {
int ok = 0; int p,u;
memset(Viz,0,sizeof(Viz));
memset(T,0,sizeof(T));
p = u = 1; C[1] = Srs; Viz[Srs] = 1;
while ( p <= u ){
int nod = C[p];
for ( int i = 0 ; i < A[nod].size() ; ++i ){
int nodvc = A[nod][i];
if ( !Viz[nodvc] && Cp[nod][nodvc] > F[nod][nodvc] ){
if ( nodvc == Dst ){
ok = 1;
continue;
}
++u; C[u] = nodvc;
Viz[nodvc] = 1; T[nodvc] = nod;
}
}
++p;
}
return ok;
}
int fluxmaxim () {
int minim,nod,nodaux;
int maxflow = 0;
while ( Bfs() ){
for ( int i = 0 ; i < A[Dst].size() ; ++i ){
nod = A[Dst][i];
minim = Cp[nod][Dst] - F[nod][Dst];
nodaux = nod;
while ( T[nodaux] ){
minim = min( minim , Cp[T[nodaux]][nodaux] - F[T[nodaux]][nodaux] );
nodaux = T[nodaux];
}
T[Dst] = nod;
nodaux = Dst;
while ( T[nodaux] ){
F[ T[nodaux] ][ nodaux ] += minim ;
F[ nodaux ][ T[nodaux] ] -= minim ;
nodaux = T[nodaux];
}
maxflow += minim;
}
}
return maxflow;
}
int main () {
fscanf(f,"%d",&N);
for ( i = 1 ; i <= N ; ++i ){
fscanf(f,"%d %d",&in,&out);
conecteaza(Srs,i,in);
conecteaza(i+N,Dst,out);
}
for ( i = 1 ; i <= N ; ++i ){
for ( j = 1 ; j <= N ; ++j ){
if ( i != j )
conecteaza(i,j+N,1);
}
}
fprintf( g,"%d\n",fluxmaxim() );
for ( i = 1 ; i <= N ; ++i ){
for ( j = 1 ; j <= N ; ++j ){
if ( i != j && F[i][j+N] == 1 )
fprintf(g,"%d %d\n",i,j);
}
}
fclose(f);
fclose(g);
return 0;
}