Pagini recente » Cod sursa (job #1893631) | Cod sursa (job #1797935) | Cod sursa (job #2025656) | Cod sursa (job #724048) | Cod sursa (job #2298341)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, maximum_flow;
int f[205];
int previous[205];
int capacity[205][205];
int flow[205][205];
vector <int> graph[205];
void reset()
{
for ( int i = 0; i <= 205; ++i )
f[i] = previous[i] = 0;
}
bool maximumFlow (int source)
{
reset();
queue <int> q;
q.push(source);
f[source] = 1;
while ( q.size() )
{
int node = q.front();
q.pop();
if ( node == 2*n+1 ) continue;
for ( auto x:graph[node] )
{
if ( !f[x] && capacity[node][x] > flow[node][x] )
{
q.push(x);
f[x] = 1;
previous[x] = node;
}
}
}
return f[2*n+1];
}
int main ()
{
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
fin>>n;
for ( int i = 1; i <= n; ++i )
{
int x, y;
fin>>x>>y;
graph[i].push_back(0);
graph[0].push_back(i);
capacity[0][i] = x;
graph[i+n].push_back(2*n+1);
graph[2*n+1].push_back(i+n);
capacity[i+n][2*n+1] = y;
for ( int j = 1; j <= n; ++j )
{
if ( i == j ) continue;
graph[i].push_back(j+n);
graph[j+n].push_back(i);
capacity[i][j+n] = 1;
}
}
while ( maximumFlow(0) )
{
for ( auto x:graph[2*n+1] )
{
if ( f[x] && capacity[x][2*n+1] > flow[x][2*n+1] )
{
previous[2*n+1] = x;
int aux = 2*n+1;
int minimum = 1e9;
while ( aux )
{
minimum = min(minimum, capacity[previous[aux]][aux]-flow[previous[aux]][aux]);
aux = previous[aux];
}
aux = 2*n+1;
while ( aux )
{
flow[aux][previous[aux]] -= minimum;
flow[previous[aux]][aux] += minimum;
aux = previous[aux];
}
maximum_flow += minimum;
}
}
}
fout<<maximum_flow<<'\n';
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
if ( i != j && flow[i][j+n] > 0 )
fout<<i<<" "<<j<<'\n';
}