Pagini recente » Cod sursa (job #1093985) | Cod sursa (job #1279422) | Cod sursa (job #1830290) | Cod sursa (job #2882157) | Cod sursa (job #3319274)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct muchie{
int x, y;
};
int cap[205][205], flow[205][205], f[205];
vector <muchie> ras;
vector <int> v[205];
bool bfs( int start, int target ){
int i, x, y;
for( i = 0; i <= target; i++ ){
f[i] = INT32_MAX / 3;
}
f[start] = 0;
queue <int> q;
q.push( start );
while( q.empty() == false ){
x = q.front();
q.pop();
for( i = 0; i < v[x].size(); i++ ){
y = v[x][i];
if( flow[x][y] < cap[x][y] && f[x] + 1 < f[y] ){
f[y] = f[x] + 1;
q.push( y );
}
}
}
return f[target] != INT32_MAX / 3;
}
int maxflow( int x, int target, int max_flow ){
int i, y, tot_flow, curr_flow;
if( max_flow == 0 ){
return 0;
}
if( x == target ){
return max_flow;
}
tot_flow = 0;
for( i = 0; i < v[x].size(); i++ ){
y = v[x][i];
if( f[x] + 1 != f[y] ){
continue;
}
curr_flow = maxflow( y, target, min( max_flow - tot_flow, cap[x][y] - flow[x][y] ) );
flow[x][y] += curr_flow;
flow[y][x] -= curr_flow;
tot_flow += curr_flow;
}
return tot_flow;
}
int main(){
int n, i, j;
ifstream fin( "harta.in" );
ofstream fout( "harta.out" );
fin >> n;
for( i = 1; i <= n; i++ ){
fin >> cap[0][i] >> cap[i + n][2 * n + 1];
v[0].push_back( i );
v[i].push_back( 0 );
v[i + n].push_back( 2 * n + 1 );
v[2 * n + 1].push_back( i + n );
}
for( i = 1; i <= n; i++ ){
for( j = 1; j <= n; j++ ){
if( i != j ){
v[i].push_back( j + n );
v[j + n].push_back( i );
cap[i][j + n] = 1;
}
}
}
while( bfs( 0, 2 * n + 1 ) ){
maxflow( 0, 2 * n + 1, INT32_MAX / 3 );
}
for( i = 1; i <= n; i++ ){
for( j = 1; j <= n; j++ ){
if( i != j && flow[i][j + n] == cap[i][j + n] ){
ras.push_back( { i, j } );
}
}
}
fout << ras.size() << '\n';
for( i = 0; i < ras.size(); i++ ){
fout << ras[i].x << ' ' << ras[i].y << '\n';
}
return 0;
}