#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

const int startIndex = 1;              // 0 or 1 for first array index
const double LARGE = numeric_limits<double>::max();

//----------------------------------------------------------------------

struct Edge
{
   double flow;
   double capacity;
};

using Digraph = vector< map<int,Edge> >;

//----------------------------------------------------------------------

void writeGraph( Digraph& g )
{
   for ( int a = startIndex; a < g.size(); a++ )
   {
      for ( const auto &pr : g[a] )
      {
         int b  = pr.first ;
         Edge e = pr.second;
         if ( e.capacity > 0.0 ) cout << a << " to " << b << "   flow: " << e.flow << "   capacity: " << e.capacity << '\n';
      }
   }
   cout << '\n';
}

//----------------------------------------------------------------------

Digraph readGraph( istream &in )
{
   int N;
   int a, b;
   double capacity;

   in >> N;
   N += startIndex;          // Keep everything 0-based internally

   Digraph g( N );
   while( in >> a >> b >> capacity )
   { 
      g[a][b] = { 0.0, capacity };
      g[b][a] = { 0.0, 0.0      };     // for a one-way edge
//    g[b][a] = { 0.0, capacity };     // for a two-way edge
   }
   return g;
}

//----------------------------------------------------------------------

vector<int> getPath( Digraph &g, int source, int target )       // find a path from source to target with spare capacity
{
   queue<int> Q;
   vector<int> predecessor( g.size(), -1 );                     // -1 signifies no predecessor on path
   
   Q.push( source );
   while( !Q.empty() )
   {
      int a = Q.front();   Q.pop();
      for ( auto &pr : g[a] )
      {
         int b = pr.first;                                      // end node for this edge
         // Check:
         //     not used             not start                 spare capacity
         if ( predecessor[b] < 0 && b != source && pr.second.capacity > pr.second.flow )
         {
            predecessor[b] = a;
            Q.push( b );
         }
         if ( predecessor[target] >= 0 ) return predecessor;    // return as soon as a path is found
      }
   }

   return predecessor;
}

//----------------------------------------------------------------------

double MaxFlow( Digraph &g, int source, int target )            // maximum flow by Edmonds-Karp algorithm
{
   double totalFlow = 0.0;                                      // the total flow from source to target

   while( true )
   {
      // Try to find path with spare capacity
      vector<int> predecessor = getPath( g, source, target );
   
      if ( predecessor[target] >= 0 )                           // found a path with capacity
      {
         double extraFlow = LARGE;
   
         // Find maximum extra flow that can be routed along this path
         for ( int b = target, a = predecessor[b]; a >= 0; b = a, a = predecessor[b] )   // source has no predecessor ( a = -1)
         {
            Edge e = g[a][b];
            extraFlow = min( extraFlow, e.capacity - e.flow );
         }
   
         // Update the current flow situation
         for ( int b = target, a = predecessor[b]; a >= 0; b = a, a = predecessor[b] )
         {
            g[a][b].flow += extraFlow;
            g[b][a].flow -= extraFlow;
         }

         // Update the total flow
         totalFlow += extraFlow;
      }
      else                                                      // no spare capacity
      {
         return totalFlow;
      }
   }
}

//======================================================================

int main()
{
   // Replace in by an ifstream if you want to read from file
   stringstream in( "7       \n"              // N
                    "1 2 3.0 \n"              // node1 node2 capacity
                    "1 4 3.0 \n"              // etc.
                    "2 3 4.0 \n"
                    "3 1 3.0 \n"
                    "3 4 1.0 \n"
                    "3 5 2.0 \n"
                    "4 5 2.0 \n"
                    "4 6 6.0 \n"
                    "5 2 1.0 \n"
                    "5 7 1.0 \n"
                    "6 7 9.0 \n" );

   Digraph g = readGraph( in );
   int source = 1, target = 7;

   cout << "Maximum flow: " << MaxFlow( g, source, target ) << "\n";

   cout << "Final graph:\n";
   writeGraph( g );
}