Pagini recente » Cod sursa (job #3256965) | Cod sursa (job #1054625) | Cod sursa (job #1294783) | Rating Damir Ferizovic (Amtrix) | Cod sursa (job #2662938)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define f in
#define g out
using namespace std;
ifstream in ( "harta.in" );
ofstream out( "harta.out" );
int n, i, j, x, y, nod, dif, fluxmax, N;
int c[220][220], flux[220][220], t[220];
vector<int> L[220];
queue<int> q;
bitset<220> viz;
int bfs(){
while ( !q.empty() )
q.pop();
viz.reset();
viz[0] = 1;
q.push(0);
while ( !q.empty() ) {
nod = q.front();
for ( auto vecin: L[nod] )
if ( !viz[vecin] && c[nod][vecin] > flux[nod][vecin] ){
q.push(vecin);
viz[vecin] = 1;
t[vecin] = nod;
if ( vecin == N )
return 1;
}
q.pop();
}
return 0;
}
int main() {
f>>n;
N = 2*n+1;
for ( i=1; i <= n; i++ ){
f>>x>>y;
L[0].push_back(i);
L[i].push_back(0);
L[n+i].push_back(N);
L[N].push_back(n+i);
c[0][i] = x;
c[n+i][N] = y;
}
for ( i=1; i <= n; i++ )
for ( j=n+1; j < N; j++ )
if ( j-i != n ){
L[i].push_back(j);
L[j].push_back(i);
c[i][j] = 1;
}
while (bfs()) {
for ( auto vecin: L[N] ){
dif = c[vecin][N] - flux[vecin][N];
if ( viz[vecin] && dif > 0 ){
x = vecin;
while ( x > 0 ) { //am pus x in loc de t[x] pentru ca exista si nodul 0
dif = min ( dif, c[t[x]][x]-flux[t[x]][x] );
x = t[x];
}
flux[vecin][N] += dif;
flux[N][vecin] -= dif;
fluxmax += dif;
x = vecin;
while ( x > 0 ) {
flux[t[x]][x] += dif;
flux[x][t[x]] -= dif;
x = t[x];
}
}
}
}
g<<fluxmax<<"\n";
for ( i=1; i <= n; i++ )
for ( j=n+1; j < N; j++ )
if ( flux[i][j] == 1 )
g<<i<<" "<<j-n<<"\n";
return 0;
}