Pagini recente » Cod sursa (job #1765740) | Cod sursa (job #1616543) | Diferente pentru implica-te/arhiva-educationala intre reviziile 154 si 153 | Cod sursa (job #2430008) | Cod sursa (job #2593531)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ( "harta.in" );
ofstream g ( "harta.out" );
const int N = 102;
struct meme{
int x, y;
}sol[N * N];
int in[N], out[N], C[2 * N][2 * N], F[2 * N][2 * N], n, tata[2 * N];
bool viz[2 * N];
vector < int > graph[2 * N];
queue < int > q;
bool bfs ( int start ){
for ( int i = 1; i <= 2 * n + 1; i++ )
viz[i] = tata[i] = 0;
q.push ( start );
viz[start] = 1;
while ( !q.empty ( ) ){
int node = q.front ( );
q.pop ( );
for ( int i = 0; i < graph[node].size ( ); i++ ){
int new_node = graph[node][i];
if ( viz[new_node] == 0 && F[node][new_node] < C[node][new_node] ){
q.push ( new_node );
tata[new_node] = node;
viz[new_node] = 1;
}
}
}
return viz[2 * n + 1];
}
int main()
{ int i, k = 0, j;
f >> n;
for ( i = 1; i <= n; i++ ){
f >> out[i] >> in[i];
}
for ( i = 1; i <= n; i++ ){
C[0][i] = out[i];
graph[0].push_back ( i );
graph[i].push_back ( 0 );
C[i + n][2 * n + 1] = in[i];
graph[i + n].push_back ( 2 * n + 1 );
graph[2 * n + 1].push_back ( n + i );
for ( j = 1; j <= n; j++ ){
if ( i != j ){
C[i][n + j] = 1;
graph[i].push_back ( n + j );
graph[n + j].push_back ( i );
}
}
}
while ( bfs ( 0 ) == 1 ){
for ( i = 0; i < graph[2 * n + 1].size ( ); i++ ){
int x = graph[2 * n + 1][i];
if ( C[x][2 * n + 1] == F[x][2 * n + 1] || viz[x] == 0 )
continue;
int Min = C[x][2 * n + 1] - F[x][2 * n + 1];
int c = x;
while ( x != 0 ){
Min = min ( Min, C[tata[x]][x] - F[tata[x]][x] );
x = tata[x];
}
x = c;
F[x][2 * n + 1] += Min;
F[2 * n + 1][x] -= Min;
while ( x != 0 ){
F[tata[x]][x] += Min;
F[x][tata[x]] -= Min;
x = tata[x];
}
}
}
for ( i = 1; i <= n; i++ ){
for ( j = 0; j < graph[i].size ( ); j++ ){
int node = graph[i][j];
if ( node != 0 && F[i][node] == C[i][node] ){
sol[++k].x = i;
sol[k].y = node - n;
}
}
}
g << k << '\n';
for ( i = 1; i <= k; i++ )
g << sol[i].x << ' ' << sol[i].y << '\n';
return 0;
}