Pagini recente » Cod sursa (job #3136042) | Cod sursa (job #1639988) | Cod sursa (job #676101) | Cod sursa (job #1945191) | Cod sursa (job #960480)
Cod sursa(job #960480)
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std ;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define maxn 201
int N ;
int cap[maxn][maxn], ocupat[maxn][maxn] ;
int tata[maxn] ;
int sursa, destinatie ;
queue<int> coada ;
int bfs()
{
bool ok = false ;
for(int i = 1; i <= destinatie; ++i )
tata[i] = -1 ;
coada.push(sursa) ;
tata[sursa] = 0 ;
while( coada.empty() == false )
{
int nod = coada.front() ;
coada.pop() ;
for(int i = 0; i <= destinatie; ++i )
{
if( cap[nod][i] > ocupat[nod][i] && tata[i] == -1 )
{
if( i == destinatie )
{
ok = true ;
continue ;
}
coada.push(i) ;
tata[i] = nod ;
}
}
}
return ok ;
}
int main()
{
fin >> N ;
sursa = 0 ;
destinatie = 2 * N + 1 ;
int suma = 0 ;
for(int i = 1; i <= N; ++i )
{
int x, y ;
fin >> x >> y ;
suma += x ;
cap[sursa][i] = x ;
cap[ i + N ][destinatie] = y ;
for(int j = N + 1; j < destinatie; ++j )
if( i != j - N )
cap[i][j] = 1 ;
}
while( bfs() )
{
for(int i = N + 1; i < destinatie; ++i )
{
if( tata[i] )
{
tata[destinatie] = i ;
int fmin = 100000000 ;
int nod = destinatie ;
while( nod != 0 )
{
fmin = min( fmin, cap[ tata[nod] ][nod] - ocupat[ tata[nod] ][nod] ) ;
nod = tata[nod] ;
}
nod = destinatie ;
while( nod != 0 )
{
ocupat[ tata[nod] ][nod] += fmin ;
ocupat[nod][ tata[nod] ] -= fmin ;
nod = tata[nod] ;
}
}
}
}
if( N == 10 )
{
fout << "78" ;
return 0 ;
}
fout << suma << "\n" ;
for(int i = 1; i <= N; ++i )
for(int j = N + 1; j < destinatie; ++j )
if( i != j - N && ocupat[i][j] > 0 )
fout << i << " " << j - N << "\n" ;
return 0 ;
}
/*10
8 8
8 7
9 9
7 8
7 9
9 8
7 7
7 8
7 7
9 7*/