#-------------------------------------------------------------
# Awk program to change DIMACS max-flow format to min-cost format
# by the following rules: 
# --Add an uncapacitated edge from sink to source, with cost -1
# --All nodes are transshipment nodes
# --All arc costs are 0
#-------------------------------------------------------------

#Change header line or flag bad header
 
(NR == 1) && ($1 == "max") {nodes = $2; arcs = $3;
	print "p", "min", nodes, arcs
 	print "c Transformed from a max-flow problem.";
			}
(NR == 1) && ($1 != "max") {print " ERROR--NOT A MAX-FLOW INPUT"; }

#Copy comment lines 
$1 == "c"	{print $0}

#Save source and sink to make new arc
($1 == "n") && ($3 == "s") {source = $2; } 
($1 == "n") && ($3 == "t") {sink = $2;}

#Copy arcs with 0 cost and 0 lower bounds 
$1 == "a"	{print $1, "\t", $2 "\t" $3 "\t" 0  "\t" $4 "\t" 0}

#Make new arc from sink to source. 
#Uncapacitated value is represented as arcs+1, which is big enough

END	{print "a","\t" sink "\t" source "\t"  0 "\t" arcs+1 ,"   \t"   -1 }