#if _MSC_VER > 1000
#else
#define __forceinline inline
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <iostream>


  

#define MAXLONG 1073741824
#define GLOB_UPDT_FREQ 0.5 //default value
#define WAVE_INIT
#define INIT_UPDATE
#undef  WAVE_INIT
//#undef INIT_UPDATE


#include <vector>


typedef  /* arc */
   struct arcSt
{
    //float           totCap;          /* total capacity */
    int             gCapIdx;       /* index in g.cap */
    float           resCap;          /* residual capacity */
    struct nodeSt   *head;           /* arc head */
    struct arcSt    *rev;            /* reverse arc */
}
  arc;

typedef  /* node */
struct nodeSt
{
    int index;            /* index in the original list of nodes */
    arc *first;           /* first outgoing arc */
    arc *current;         /* current outgoing arc */
    double excess;        /* excess at the node
			     change to double if needed */
    /* double excess; */
    long d;                /* distance label */
    struct nodeSt *bNext;  /* next node in bucket */
    struct nodeSt *bPrev;  /* previous node in bucket */
} node;


typedef /* bucket */
  struct bucketSt
{
  node *firstActive;      /* first node with positive excess */
  node *firstInactive;    /* first node with zero excess */
} bucket;


typedef 
  struct solutionSgt
{
  std::vector<int> indicator_vector; 
  float beta1; 
  float beta2; 
} solutionSgt;


typedef 
  struct solutionSz
{
  bool true_solution; 
  float brkpt_or_h; 
  std::vector<int> indicator1; 
  std::vector<int> indicator2; 
} solutionSz;



class hi_pr{
public:
	/* global variables */

	long   n;                    /* number of nodes */
	long   m;                    /* number of arcs */
	long   nm;                   /* n + ALPHA * m */
	long   nMin;                 /* smallest node id */
	node   *nodes;               /* array of nodes */
	arc    *arcs;                /* array of arcs */
	bucket *buckets;             /* array of buckets */
	float  *cap;                 /* array of capacities */
	node   *source;              /* source node pointer */
	node   *sink;                /* sink node pointer */
	long   dMax;                 /* maximum label */
	long   aMax;                 /* maximum actie node label */
	long   aMin;                 /* minimum active node label */
	/* excessType flow;             /\* flow value *\/ */
	double flow;             /* flow value */
	long pushCnt;                /* number of pushes */
	long relabelCnt;             /* number of relabels */
	long updateCnt;              /* number of updates */
	long gapCnt;                 /* number of gaps */
	long gNodeCnt;               /* number of nodes after gap */  
	float t, t2;                 /* for saving times */
	node  *sentinelNode;        /* end of the node list marker */
	arc *stopA;                  /* used in forAllArcs */
	long workSinceUpdate;        /* the number of arc scans since last update */
	float globUpdtFreq;          /* global update frequency */
	//
	long i_dist;
	//
	node *i_next, *i_prev;
public:
	hi_pr();
	int allocDS();/*!< allocate datastructures, initialize related variables */
	void init();
	void checkMax();
	void multiply(float lbd);
	void globalUpdate();/*!< global update via backward breadth first search from the sink */
	void stageOne();/*!< first stage  -- maximum preflow*/
	/* long long cut_cost(); */
	double cut_cost(); 
	int main(float glob_update_freq);
	bool is_weak_source(node * v);
public:
	template<typename tcap> 
	void construct(int nV, int nE, const int * E, const tcap * cap, const tcap * excess);
	/* void construct(int nV, int nE, const tcap * E, const tcap * cap, const tcap * excess); */
	void construct(const char * filename);
	~hi_pr(){
		destroy();
	};
	void destroy();
	int parse(long *n_ad, long *m_ad, node **nodes_ad, arc **arcs_ad, float **cap_ad, node **source_ad, node    **sink_ad, long *node_min_ad);
private:
	__forceinline int gap (bucket *emptyB); /*!< gap relabeling */
	__forceinline long relabel(node *i);/*!<--- relabelling node i */
	__forceinline void discharge(node *i);/*!< discharge: push flow out of i until i becomes inactive */
	void wave();//!< go from higher to lower buckets, push flow
public:
	double flow0;             /* added flow value */
	void add_arc(int tail, int head, float cap1, float cap2, long *& arc_first, long *& arc_tail, long & pos_current, arc *& arc_current, node *& nodes, long & node_min, long & node_max, long & no_alines);
};


float timer();


#define ALPHA 6//閾値をALPHA * n + mとし，
#define BETA 12//relable1回でworkSINCEUPDATEをBETA増やす．


#define WHITE 0
#define GREY 1
#define BLACK 2


/* macros */

#define forAllNodes(i) for ( i = nodes; i != sentinelNode; i++ )
#define forAllRegularNodes(i) for ( i = nodes; i != sentinelNode && i-nodes<nV; i++ ) //謎 nVってなに
#define forAllArcs(i,a) for (a = i->first, stopA = (i+1)->first; a != stopA; a++) // node iの全枝を探索

#define nNode( i ) ( (i) - nodes + nMin )//nodeの番号返す
#define nArc( a )  ( ( a == NULL )? -1 : (a) - arcs )//枝の番号返す

#define min( a, b ) ( ( (a) < (b) ) ? a : b )

#define aAdd(l,i)				\
  {						\
    i->bNext = l->firstActive;			\
    l->firstActive = i;				\
    i_dist = i->d;				\
    if (i_dist < aMin)				\
      aMin = i_dist;				\
    if (i_dist > aMax)				\
      aMax = i_dist;				\
    if (dMax < aMax)				\
      dMax = aMax;				\
  }

/* i must be the first element */ //バケットlのアクティブ頂点iを取り除く.iはリストの先頭である必要
#define aRemove(l,i)				\
  {						\
    l->firstActive = i->bNext;			\
  }

// バケットlにinactive頂点を加える． inactive頂点の管理方法は，active頂点と違い双方向リストであることに注意
#define iAdd(l,i)				\
  {						\
    i_next = l->firstInactive;			\
    i->bNext = i_next;				\
    i->bPrev = sentinelNode;			\
    i_next->bPrev = i;				\
    l->firstInactive = i;			\
  }

//バケットlからinactive頂点iを取り除く． 先頭からじゃなくてもよい．
#define iDelete(l,i)				\
  {						\
    i_next = i->bNext;				\
    if (l->firstInactive == i) {		\
      l->firstInactive = i_next;		\
      i_next->bPrev = sentinelNode;		\
    }						\
    else {					\
      i_prev = i->bPrev;			\
      i_prev->bNext = i_next;			\
      i_next->bPrev = i_prev;			\
    }						\
  }

/* allocate datastructures, initialize related variables */



#ifndef WIN32
//#include <resource.h>

float timer ()
{
  clock_t tt = clock();
  return (float)(double(tt)/CLOCKS_PER_SEC);
}

#else

float timer (){
  return 0;
};

#endif




hi_pr::hi_pr(){// hi_prの初期化関数
};

int hi_pr::allocDS( ){//bucketsと番兵の初期化
  // std::cout << "hi_pr::allocDS()" << std::endl;
  nm = ALPHA * n + m;//謎のnm
  /*
    queue = (node**) calloc ( n, sizeof (node*) );
    if ( queue == NULL ) return ( 1 );
    qLast = queue + n - 1;
    qInit();
  */
  buckets = (bucket*) calloc ( n+2, sizeof (bucket) );//buckets[k]はラベルkを持つactive, inactive両方の頂点のリストの先頭を指すポインタを持つ．
                                                       //node structureは，リスト上での次のnodeを指すポインタを持つ
  if ( buckets == NULL ) return ( 1 );

  sentinelNode = nodes + n;//sentinel...番兵
  sentinelNode->first = arcs + 2*m;//番兵のfirst edgeをm+1番目のedgeに指定

  return ( 0 );

} /* end of allocate */


void hi_pr::init( )
{
  // std::cout << "hi_pr::init()" << std::endl;
  node  *i;        /* current node */
  int overflowDetected;
  bucket *l;
  arc *a;
  // #ifdef EXCESS_TYPE_LONG
  //   double testExcess;
  // #endif
  // #ifndef OLD_INIT
  //   unsigned long delta;
  // #endif

  double testExcess;
  double delta;

  // initialize excesses
  
  forAllNodes(i) {
    i->excess = 0;
    i->current = i->first;
    forAllArcs(i, a){
      a->resCap = cap[a-arcs];// 枝への順番の付け方が，隣接する頂点が若い順につけている感じだ．
                               // なので，今注目している枝のポインタ - arcs で枝のidが分かる．
                               //各枝のrescapは，初期化段階では0ではないんか? ←　rescapは，その枝の残り容量．residual graphでの容量ではない.
      // std::cout << "resCap: " << cap[a-arcs] << std::endl;
    }
  }
  
  //AS: ?error: l=buckets + n is not initialized, and globalUpdate can go up to n, which must be sentinelNode
  for (l = buckets; l <= buckets + n-1; l++) {//バケットの初期化．各ポインタを番兵nodeに向かわせる
    l -> firstActive   = sentinelNode;
    l -> firstInactive  = sentinelNode;
  }
  
  overflowDetected = 0;

#ifdef OLD_INIT//灰色の文字なのは仕様
  source -> excess = MAXLONG;
#else
  if (overflowDetected) {//overflowを判定する部分がコメントアウトされてるのでこのif文は実質意味なし
    source -> excess = MAXLONG;
  }
  else {
    source->excess = 0;// sourceはsource nodeへのポインタ
    forAllArcs(source,a) {
      if (a->head != source) {// 自己ループ判定
	pushCnt ++;
   //以下，枝容量目いっぱいながす
	delta = a -> resCap;
	// std::cout << "delta: " << delta << std::endl;
	a -> resCap -= delta;
	(a -> rev) -> resCap += delta;// residual graphは，逆向きの枝を張ることで表現
	// std::cout << "resCap: " << a->resCap << std::endl;
	// std::cout << "revResCap: " << a -> rev -> resCap  << std::endl;
	a->head->excess += delta;
	// std::cout << "a->head->excess: " << a -> head -> excess  << std::endl;
      }
    }
  }
  
  /*  setup labels and buckets */
  l = buckets + 1;//ラベル1のバケットを指し示すポインタ
  
  aMax = 0;//これらの更新は，aAdd内部でされる
  aMin = n;
  
  //各nodeのラベリングと，bucketへのセッティング
  forAllNodes(i) {
    if (i == sink) {
      i->d = 0;
      iAdd(buckets,i);
      continue;
    }
    if ((i == source) && (!overflowDetected)) {
      i->d = n;
    }
    else
      i->d = 1;
    if (i->excess > 0) {
      /* put into active list */
      aAdd(l,i);
    }
    else { /* i -> excess == 0 */
      /* put into inactive list */
      if (i->d < n)
	iAdd(l,i);
    }
  }
  dMax = 1;
#endif
  
  //  dMax = n-1;
  //  flow = 0.0;

} /* end of init */



void hi_pr::checkMax()
{//maxとなっているラベルが正しいかの確認頂点が含まれていないbucketが番兵を指しているかの確認
  // std::cout << "hi_pr::checkMax()" << std::endl;
  bucket *l;

  for (l = buckets + dMax + 1; l < buckets + n; l++) {
    assert(l->firstActive == sentinelNode);
    assert(l->firstInactive == sentinelNode);
  }
}


void hi_pr::multiply(float lbd){//各枝の容量をlbd倍する　何の意味が有るかは知らん
  // std::cout << "hi_pr::multiply()" << std::endl;
  /* Multiply the capacities by the coefficient lbd */
  node *node_i;
  arc  *edge_a;
  int counter = 0;
  forAllNodes(node_i){
    forAllArcs(node_i, edge_a){
	counter++;
	edge_a->resCap *= lbd;

    }
  }
  for (int i=0; i<2*m; i++){
    cap[i] *= lbd;
  }
  // std::cout << "total number of edges: " << m*2 << std::endl;
}




/* global update via backward breadth first search from the sink */

void hi_pr::globalUpdate ()
{
  // std::cout << "hi_pr::globalUpdate()" << std::endl;

  node  *i, *j;       /* node pointers */
  arc   *a;           /* current arc pointers  */
  bucket *l, *jL;          /* bucket */
  long curDist, jD;
  long state;

  updateCnt ++;

  /* initialization */
  forAllNodes(i)
    i -> d = n;
  sink -> d = 0;

  for (l = buckets; l <= buckets + dMax; l++) {
    l -> firstActive   = sentinelNode;
    l -> firstInactive  = sentinelNode;
  }

  dMax = aMax = 0;
  aMin = n;

  /* breadth first search */
  // add sink to bucket zero

  iAdd(buckets, sink);
  for (curDist = 0; 1; curDist++) {

    state = 0;
    l = buckets + curDist;
    jD = curDist + 1;
    jL = l + 1;
    /*
      jL -> firstActive   = sentinelNode;
      jL -> firstInactive  = sentinelNode;
    */

    if ((l->firstActive == sentinelNode) && 
	(l->firstInactive == sentinelNode))
      break;

    while (1) {

      switch (state) {
      case 0: 
	i = l->firstInactive;
	state = 1;
	break;
      case 1:
	i = i->bNext;
	break;
      case 2:
	i = l->firstActive;
	state = 3;
	break;
      case 3:
	i = i->bNext;
	break;
      default: 
	assert(0);
	break;
      }

      if (i == sentinelNode) {
	if (state == 1) {
	  state = 2;
	  continue;
	}
	else {
	  assert(state == 3);
	  break;
	}
      }

      /* scanning arcs incident to node i */
      // std::cout << "node " << i << " ";
      forAllArcs(i,a) {
	// std::cout << "< " << a->rev->resCap << " ";
	if (a->rev->resCap > 0 ) {
	  j = a->head;
	  if (j->d == n) {
	    j->d = jD;
	    j->current = j->first;
	    if (jD > dMax) dMax = jD;

	    if (j->excess > 0) {
	      /* put into active list */
	      aAdd(jL,j);
	    }
	    else {
	      /* put into inactive list */
	      iAdd(jL,j);
	    }
	  }
	}
      } /* node i is scanned */ 
      // std::cout << std::endl;
    }
  }

} /* end of global update */




/* second stage -- preflow to flow */




/* gap relabeling */
//
int hi_pr::gap(bucket *emptyB){
  // std::cout << "hi_pr::gap()" << std::endl;

  bucket *l;
  node  *i; 
  long  r;           /* index of the bucket before l  */
  int   cc;          /* cc = 1 if no nodes with positive excess before
			the gap */

  gapCnt ++;
  r = ( emptyB - buckets ) - 1;

  /* set labels of nodes beyond the gap to "infinity" */
  for ( l = emptyB + 1; l <= buckets + dMax; l ++ ) {
    // this does nothing for high level selection

    for ( i = l -> firstInactive; i != sentinelNode; i = i -> bNext ) {
      i -> d = n;
      gNodeCnt ++;//ギャップリラベリングした頂点の数かな
    }

    l -> firstInactive = sentinelNode;
  }

  cc = ( aMin > r ) ? 1 : 0;

  dMax = r;
  aMax = r;

  return ( cc );

}


/*--- relabelling node i */
long hi_pr::relabel(node *i){/* node to relabel */
  // std::cout << "hi_pr::relabel()" << std::endl;
  
  node  *j;
  long  minD;     /* minimum d of a node reachable from i */
  arc   *minA;    /* an arc which leads to the node with minimal d */
  arc   *a;

  assert(i->excess > 0);//アクティブであることを確認

  relabelCnt++;
  workSinceUpdate += BETA;

  i->d = minD = n;
  minA = NULL;

  /* find the minimum */
  forAllArcs(i,a) {
    workSinceUpdate++;
    if (a -> resCap > 0) {
      j = a -> head;
      if (j->d < minD) {
	minD = j->d;
	minA = a;
      }
    }
  }

  minD++;

  if (minD < n) {

    i->d = minD;
    i->current = minA;//currentより前の枝はfeasibleじゃない

    if (dMax < minD) dMax = minD;// 最大ラベルの更新

  } /* end of minD < n */

  return ( minD );

} /* end of relabel */



void hi_pr::discharge (node  *i){


  node  *j;                 /* sucsessor of i */
  long  jD;                 /* d of the next bucket */
  bucket *lj;               /* j's bucket */
  bucket *l;                /* i's bucket */
  arc   *a;                 /* current arc (i,j) */
  double  delta;
  arc *stopA;

  assert(i->excess > 0);
  assert(i != sink);

  do {

    jD = i->d - 1;//iのラベルより1小さい頂点に流す
    l = buckets + i->d;


    for (a = i->current, stopA = (i+1)->first; a != stopA; a++) {
      if (a -> resCap > 0) {
	j = a -> head;

	if (j->d == jD) {//(i,j)がfeasibleなら
	  pushCnt ++;
	  if (a->resCap < i->excess)
	    delta = a->resCap;
	  else
	    delta = i->excess;
	  a->resCap -= delta;
	  a->rev->resCap += delta;


	  if (j != sink) {

	    lj = buckets + jD;

	    if (j->excess == 0) {//jがもともとinactiveなら，activeバケットに移す
	      /* remove j from inactive list */
	      iDelete(lj,j);
	      /* add j to active list */
	      aAdd(lj,j);
	    }
	  }

	  j -> excess += delta;
	  i -> excess -= delta;

	  if (i->excess == 0) break;

	} /* j belongs to the next bucket */
      } /* a  is not saturated */
    } 

    if (a == stopA) {
      /* i must be relabeled */
      relabel (i);//relabelした後もaADDは行わない． iがinactiveになるまでiからpushし続け，最後はiADDで対応する
      if (i->d == n) break;
      if ((l -> firstActive == sentinelNode) && (l -> firstInactive == sentinelNode)){//iをリラベルしたことによって，lが空になったら
	gap(l);
      };
      if (i->d == n) break;
    }
    else {
      /* i no longer active */
      i->current = a;
      /* put i on inactive list */
      iAdd(l,i);//iをinactive bucketに加える
      break;
    }
  } while (1);
}

void hi_pr::wave() {
  
  node   *i;
  bucket  *l;

  for (l = buckets + aMax; l > buckets; l--) {
    for (i = l->firstActive; i != sentinelNode; i = l->firstActive) {
      aRemove(l,i);

      assert(i->excess > 0);
      discharge (i);

    }
  }
}



/* first stage  -- maximum preflow*/
void hi_pr::stageOne ( )
{
  // std::cout << "hi_pr::stageOne()" << std::endl;

  node   *i;
  bucket  *l;             /* current bucket */

#if defined(INIT_UPDATE) || defined(OLD_INIT) || defined(WAVE_INIT)
  globalUpdate ();//最初にglobalupdateするかどうか
#endif

  workSinceUpdate = 0;

#ifdef WAVE_INIT
  wave();
#endif  


  while ( aMax >= aMin ) {//aMINは小さくなることはあっても大きくなることはない．
                          //aMax < aMinとなるのは，全てのactive頂点のラベルがn以上になった時．
    l = buckets + aMax;
    i = l->firstActive;
    
    if (i == sentinelNode)
      aMax--;//aMaxを減少させるのは，ここだけ．aMaxが増加するのはaADDだけ．
    else {
      aRemove(l,i);
      
      assert(i->excess > 0);
      discharge (i);
      
      if (aMax < aMin)
	break;
      
      /* is it time for global update? */
      if (workSinceUpdate * globUpdtFreq > nm) {
	globalUpdate();
	workSinceUpdate = 0;
      }
      
    }
    
  } /* end of the main loop */
  
  flow = sink->excess + flow0;//flow0とは？

} 


int hi_pr::main(float glob_update_freq){//コマンドライン引数はgloba lupdate frequency  (ALPHA * n + m) / global_update_frequency が閾値
  // std::cout << "hi_pr::main()" << std::endl;
  globUpdtFreq =  glob_update_freq;



  parse( &n, &m, &nodes, &arcs, &cap, &source, &sink, &nMin );//parse定義されてないぞ．parser.cppからもってくるのかな

  int cc;
  cc = allocDS();
  if ( cc ) { fprintf ( stderr, "Allocation error\n"); exit ( 1 ); }

  t = timer();
  t2 = t;

  init();
  stageOne ( );

  t2 = timer() - t2;

  printf ("%d\n", int(flow));





  exit(0);

}


bool hi_pr::is_weak_source(node * v){
  // std::cout << "hi_pr::is_weak_source()" << std::endl;
  return v->d>=n;
};


double hi_pr::cut_cost(){
  return 1;
};




int hi_pr::parse(long *n_ad, long *m_ad, node **nodes_ad, arc **arcs_ad, float **cap_ad, node **source_ad, node    **sink_ad, long *node_min_ad)
{

#define MAXLINE       100	/* max line length in the input file */
#define ARC_FIELDS      3	/* no of fields in arc line  */
#define NODE_FIELDS     2	/* no of fields in node line  */
#define P_FIELDS        3       /* no of fields in problem line */
#define PROBLEM_TYPE "max"      /* name of problem type*/


	long    n,                     
		node_min=0,          
		node_max=0,           
		*arc_first=NULL,   *arc_tail = NULL,      /* internal array for holding
								 *arc_tail=NULL,          /* internal array: tails of the arcs */
								 source=0,               /* no of the source */
								 sink=0,                 /* no of the sink */
								 /* temporary variables carrying no of nodes */
								 head, tail, i;

	long    m,            
		last, arc_num, arc_new_num;

	node    *nodes=NULL,            /* pointer to the node structure */
		*head_p,
		*ndp;

	arc     *arcs=NULL,             /* pointer to the arc structure */
		*arc_current=NULL,
		*arc_new,
		*arc_tmp;

	float  *acap=NULL,             /* array of capacities */
		cap;                    /* capacity of the current arc */

	long    no_lines=0,             /* no of current input line */
		no_plines=0,            /* no of problem-lines */
		no_nslines=0,           /* no of node-source-lines */
		no_nklines=0,           /* no of node-source-lines */
		no_alines=0,            /* no of arc-lines */
		pos_current=0;          /* 2*no_alines */

	char    in_line[MAXLINE],       /* for reading input line */
		//AS: was pr_type[3] and this was causing a bug (MSVC compiler)
		pr_type[4],             /* for reading type of the problem */
		nd;                     /* source (s) or sink (t) */

	int     k,                      /* temporary */
		err_no;                 /* no of detected error */

    scanf ( "%ld %ld", &n, &m );
    nodes    = (node*) calloc ( n+2, sizeof(node) );//!< +1 for 0'th node, when numbering in file starts from 1, +1 for sentinelNode
    arcs     = (arc*)  calloc ( 2*m+1, sizeof(arc) );//reverse edgeのために2倍．番兵用にプラス1
    arc_tail = (long*) calloc ( 2*m,   sizeof(long) ); 
    arc_first= (long*) calloc ( n+2, sizeof(long) );//各ノードのfirst edge
    acap     = (float*) calloc ( 2*m, sizeof(float) );//容量
    arc_current = arcs;
    source = 0;
    node_max = 0;
	node_min = n;
    sink = n-1;


	for(int ii = 0; ii < m ; ii ++)
	{

	scanf ( "%ld %ld %f",&tail, &head, &cap );


			/* no of arcs incident to node i is stored in arc_first[i+1] */
			arc_first[tail + 1] ++; 
			arc_first[head + 1] ++;

			/* storing information about the arc */
			assert(pos_current+1<2*m);
			arc_tail[pos_current]        = tail;
			arc_tail[pos_current+1]      = head;
			assert(arc_current-arcs >=0 && arc_current-arcs+1 < 2*m+1);
			arc_current       -> head    = nodes + head;
			arc_current       -> resCap    = cap;
			arc_current       -> rev  = arc_current + 1;
			( arc_current + 1 ) -> head    = nodes + tail;
			( arc_current + 1 ) -> resCap    = 0;
			( arc_current + 1 ) -> rev  = arc_current;

			/* searching minimumu and maximum node */
			if ( head < node_min ) node_min = head;
			if ( tail < node_min ) node_min = tail;
			if ( head > node_max ) node_max = head;
			if ( tail > node_max ) node_max = tail;

			no_alines   ++;
			arc_current += 2;
			pos_current += 2;

	}     /* end of input loop */

	/* ----- all is red  or  error while reading ----- */ 


	//AS: this is a fix for sink, having no incoming arcs
	node_max = n-1+node_min;

	/********** ordering arcs - linear time algorithm ***********/

	/* first arc from the first node */
	( nodes + node_min ) -> first = arcs;


	for ( i = node_min + 1; i <= node_max + 1; i ++ ) 
	{
		arc_first[i]          += arc_first[i-1];
		( nodes + i ) -> first = arcs + arc_first[i];
	}


	for ( i = node_min; i < node_max; i ++ ) /* scanning all the nodes  
											 exept the last*/
	{

		last = ( ( nodes + i + 1 ) -> first ) - arcs;
		for ( arc_num = arc_first[i]; arc_num < last; arc_num ++ )
		{ tail = arc_tail[arc_num];

		while ( tail != i )

		{ arc_new_num  = arc_first[tail];
		arc_current  = arcs + arc_num;
		arc_new      = arcs + arc_new_num;

		head_p               = arc_new -> head;
		arc_new -> head      = arc_current -> head;
		arc_current -> head  = head_p;

		cap                 = arc_new -> resCap;
		arc_new -> resCap     = arc_current -> resCap;
		arc_current -> resCap = cap;

		if ( arc_new != arc_current -> rev )
		{
			arc_tmp                = arc_new -> rev;
			arc_new  -> rev     = arc_current -> rev;
			arc_current -> rev  = arc_tmp;

			( arc_current -> rev ) -> rev = arc_current;
			( arc_new     -> rev ) -> rev = arc_new;
		}

		arc_tail[arc_num] = arc_tail[arc_new_num];
		arc_tail[arc_new_num] = tail;

		/* we increase arc_first[tail]  */
		arc_first[tail] ++ ;

		tail = arc_tail[arc_num];
		}
		}
		/* all arcs outgoing from  i  are in place */
	}       

	for ( ndp = nodes + node_min; ndp <= nodes + node_max;  ndp ++ )
		ndp -> first = (arc*) NULL;

	for ( arc_current = arcs + (2*m-1); arc_current >= arcs; arc_current -- )
	{
		arc_num = arc_current - arcs;
		tail = arc_tail [arc_num];
		ndp = nodes + tail;
		/* avg
		arc_current -> next = ndp -> first;
		*/
		ndp -> first = arc_current;
	}

	//AS: this is a fix for nodes, not having outcoming arcs
	for ( ndp = nodes + node_max; ndp >= nodes + node_min;  --ndp){
		if(!ndp->first){
			ndp->first=(ndp+1)->first;
		};
	};

	/* ----------- assigning output values ------------*/
	*m_ad = m;
	*n_ad = node_max - node_min + 1;
	*source_ad = nodes + source;
	*sink_ad   = nodes + sink;
	*node_min_ad = node_min;
	*nodes_ad = nodes + node_min;
	*arcs_ad = arcs;
	*cap_ad = acap;

	for ( arc_current = arcs, arc_num = 0; 
		arc_num < 2*m;
		arc_current ++, arc_num ++
		)
		acap [ arc_num ] = arc_current -> resCap; 



	/* free internal memory */
	free ( arc_first ); free ( arc_tail );

	/* Thanks God! all is done */
	return (0);

	/* ---------------------------------- */

}

void hi_pr::destroy(){

}



signed main(){
  hi_pr h;
  h.main(0.5);

}


Measured memory_bytes: 3336