Pagini recente » Cod sursa (job #1048081) | Cod sursa (job #678091) | Cod sursa (job #703066) | Cod sursa (job #3150970) | Cod sursa (job #960077)
Cod sursa(job #960077)
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std ;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define maxn 202
#define inf ( 1 << 31 ) - 1
int N ;
int cap[maxn][maxn], ocupat[maxn][maxn] ;
int tata[maxn] ;
int sursa, destinatie ;
int bfs()
{
queue<int> coada ;
bool ok = false ;
memset( tata, -1, sizeof(tata) ) ;
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 = inf ;
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] ;
}
}
}
}
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 ;
}