Pagini recente » Cod sursa (job #2800941) | Cod sursa (job #2495001) | Cod sursa (job #2605845) | Cod sursa (job #467869) | Cod sursa (job #2895302)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100;
vector <int> edges[2 * NMAX + 2];
int flux[2 * NMAX + 2][2 * NMAX + 2];
int p[2 * NMAX + 2];
int s, d, n;
bool bfs() {
queue <int> q;
for ( int i = 0; i <= 2 * n + 1; i ++ ) p[i] = -1;
p[s] = -2;
q.push( s );
while ( !q.empty() ) {
int node = q.front();
q.pop();
for ( auto it : edges[node] ) {
if ( p[it] != -1 || flux[node][it] <= 0 ) continue;
p[it] = node;
q.push( it );
}
}
return ( p[d] != -1 );
}
int main() {
ifstream fin( "harta.in" );
ofstream fout( "harta.out" );
fin >> n;
s = 0, d = 2 * n + 1;
for ( int i = 1; i <= n; i ++ ) {
int in, out;
fin >> out >> in;
edges[s].push_back( i );
edges[i].push_back( s );
flux[s][i] = out;
flux[i][s] = 0;
edges[d].push_back( i + n );
edges[i + n].push_back( d );
flux[i + n][d] = in;
flux[d][i + n] = 0;
}
for ( int i = 1; i <= n; i ++ ) {
for ( int j = n + 1; j <= 2 * n; j ++ ) {
if ( i + n == j ) continue;
edges[i].push_back( j );
edges[j].push_back( i );
flux[i][j] = 1;
}
}
int flow = 0;
while ( bfs() ) {
for ( auto node : edges[d] ) {
if ( flux[node][d] <= 0 || p[node] == -1 ) continue;
int maxflow = flux[node][d];
for ( int i = node; i != s; i = p[i] ) {
maxflow = min( maxflow, flux[p[i]][i] );
}
flux[node][d] -= maxflow;
flux[d][node] += maxflow;
for ( int i = node; i != s; i = p[i] ) {
flux[p[i]][i] -= maxflow;
flux[i][p[i]] += maxflow;
}
flow += maxflow;
}
}
fout << flow << '\n';
for ( int i = 1; i <= n; i ++ ) {
for ( int j = n + 1; j <= 2 * n; j ++ ) {
if ( i + n != j && flux[i][j] == 0 )
fout << i << ' ' << j - n << '\n';
}
}
return 0;
}