Pagini recente » Istoria paginii utilizator/andreitimofte | Cod sursa (job #992909)
Cod sursa(job #992909)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
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';
}
}