Cod sursa(job #992913)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
/**
Putem modela problema cu ajutorul unei retele de flux.
O sa construim un graf bipartit cu cele N noduri in ablele parti si vom adauga
o sursa si o destinatie. Costurile vor fi urmatoarele:
- muchie in graf bipartit - cost 1
- muchie de la sursa la stanga - cost de intrare
- muchie de la dreapta la destinatie - cost de iesire
Avem garantia ca fluxul maxim va alege muchiile astefel incat sa gradele de intrare
si iesire vor fi respectate. Nu este solutie cand suma gradelor de intrare si iesire
sunt diferite sau cand aceasta suma nu e egala cu fluxul maxim gasit.
*/
ifstream F("harta.in");
ofstream G("harta.out");
const int Nmax = 210;
int N,M,dad[Nmax],total_in,total_out;
int capacity[Nmax][Nmax];
bool mark[Nmax],in_queue[Nmax];
int BF()
{
queue<int> Q;
Q.push( 0 );
dad[0] = -1;
in_queue[0] = 1;
while ( Q.size() )
{
int node = Q.front(); Q.pop();
if ( mark[node] == 1 ) continue;
mark[node] = 1;
for (int i=0;i<=M;++i)
if ( capacity[node][i] > 0 )
if ( in_queue[i] == 0 )
{
in_queue[i] = 1;
dad[i] = node;
Q.push(i);
}
}
if ( mark[M] )
return 1;
return 0;
}
int main()
{
F>>N; M=2*N+1;
for (int i=1,in,out;i<=N;++i)
{
F>>in>>out;
capacity[0][i] = in;
capacity[N+i][M] = out;
total_in += in;
total_out += out;
}
for (int i=1;i<=N;++i)
for (int j=N+1;j<M;++j)
if ( i != j-N )
capacity[i][j] = 1;
while ( BF() )
{
for (int i=N+1;i<M;++i)
if ( capacity[i][M] && mark[i] )
{
int actual_flow = capacity[i][M], node = i;
while ( node != 0 )
{
actual_flow = min(actual_flow,capacity[dad[node]][node]);
node = dad[node];
}
node = i , capacity[node][M] -= actual_flow;
while ( node != 0 )
{
capacity[dad[node]][node] -= actual_flow;
capacity[node][dad[node]] += actual_flow;
node = dad[node];
}
}
memset(dad,0,sizeof(dad));
memset(mark,0,sizeof(mark));
memset(in_queue,0,sizeof(in_queue));
}
queue<pair<int,int> > edges;
for (int i=1;i<=N;++i)
for (int j=N+1;j<M;++j)
if ( capacity[j][i] > 0 )
edges.push( make_pair(i,j-N) );
int nr_edges = edges.size();
if ( total_in != total_out || total_in != nr_edges )
{
G<<"-1\n";
return 0;
}
G<<nr_edges<<'\n';
while ( edges.size() )
{
int x = edges.front().first;
int y = edges.front().second;
edges.pop();
G<<x<<' '<<y<<'\n';
}
}