Internet connection

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;


public class MaxFlowSolver {
	private int[][] capacities;
	private int[][] labels;
	private int[][] flowAmounts;
	private boolean[] isNodeCheckedArray;
	
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        MaxFlowSolver solver = new MaxFlowSolver(parseInputToCapacities(scan));
        System.out.println(solver.calculateMaxFlow());
        scan.close();
    }
    
    public static int[][] parseInputToCapacities(Scanner scanner) {
    	int amountNodes = scanner.nextInt();
    	int amountConnectionsNotProcessed = scanner.nextInt();
    	int[][] capacities = new int[amountNodes][amountNodes];
    	
    	while(amountConnectionsNotProcessed > 0) {
    		capacities[scanner.nextInt()-1][scanner.nextInt()-1] = scanner.nextInt();
    		amountConnectionsNotProcessed--;
    	}
    	return capacities;
    }
    
    public MaxFlowSolver(int[][] capacities) {
    	this.capacities = capacities;
    	this.flowAmounts = new int[getAmountNodes()][getAmountNodes()];
    	this.isNodeCheckedArray = new boolean[getAmountNodes()];
    }
    
    public int[] getLabelAtNode(int node) {
    	return labels[node];
    }
    
    public boolean isNodeLabeled(int node) {
    	return labels[node][1] > -1;
    }
    
    public boolean isEndNodeLabeled() {
    	return isNodeLabeled(getAmountNodes() -1);
    }
    
    public boolean isNodeChecked(int node) {
    	return isNodeCheckedArray[node];
    }
    
    public void setNodeChecked(int node, boolean value) {
    	isNodeCheckedArray[node] = value;
    }
    
    public boolean isEdgeExistent(int sourceNode, int targetNode) {
    	return getEdgeCapacity(sourceNode, targetNode) > 0;
    }
    
    public int getEdgeCapacity(int sourceNode, int targetNode) {
    	return capacities[sourceNode][targetNode];
    }
    
    public int getEdgeFlow(int sourceNode, int targetNode) {
    	return flowAmounts[sourceNode][targetNode];
    }
    
    public int getCurrentFlow() {
    	return IntStream.of(flowAmounts[0]).sum();
    }
    
    public int getAmountNodes() {
    	return this.capacities.length;
    }
    
    public void setLabel(int node, int deltaNode, int delta) {
    	labels[node][0] = deltaNode;
    	labels[node][1] = delta;
    }
    
    public boolean isGoodEdge(int sourceNode, int targetNode) {
    	return getEdgeCapacity(sourceNode, targetNode) > 0;
    }
    
    
    public void clearLabels() {
    	this.labels = new int[getAmountNodes()][2];
    	for(int[] nodeLabel: labels) {
    		nodeLabel[0] = -1;
    		nodeLabel[1] = -1;
    	}
    	this.labels[0][1] = Integer.MAX_VALUE;
    }
    
    public void clearNodesChecked() {
    	Arrays.fill(isNodeCheckedArray, false);
    }
    
    public int calculateMaxFlow() {
    	clearLabels();
    	clearNodesChecked();
    	
    	while(!isEndNodeLabeled()) {
    		int nextNodeToCheck = getNextUncheckedNodeWithLabel();    		
        	if(nextNodeToCheck == -1) { //Done
        		return getCurrentFlow();
        	}
        	else {
        		setNodeChecked(nextNodeToCheck, true);
        		labelNeighbourNodes(nextNodeToCheck);
        	}        	
    	}
    	upgradeFlow();
		return calculateMaxFlow();
    	
    }
    
    public int getNextUncheckedNodeWithLabel() {
//    	for(int node = 0; node < getAmountNodes(); node++) {
//    		if(!isNodeChecked(node) && isNodeLabeled(node)) {
//    			return node;
//    		}
//    	}
    	for(int node = getAmountNodes()-1; node >= 0; node--) {
    		if(!isNodeChecked(node) && isNodeLabeled(node)) {
    			return node;
    		}
    	}
    	return -1;
    }
    
    public void labelNeighbourNodes(int node) { // TODO
    	int delta = getLabelAtNode(node)[1];
    	int nextNeighbourToCheck = 0;
    	while (nextNeighbourToCheck < getAmountNodes()) {
    		if(nextNeighbourToCheck != node) {
    			if(isEdgeExistent(node, nextNeighbourToCheck)) {
    				int flow = getEdgeFlow(node, nextNeighbourToCheck);
    				int capacity = getEdgeCapacity(node, nextNeighbourToCheck);
    				int diffFlowCapacity = capacity - flow;
    				if(diffFlowCapacity > 0) {
    					setLabel(nextNeighbourToCheck, node, Math.min(delta, diffFlowCapacity));
    				}
    				
    			}
    			if(isEdgeExistent(nextNeighbourToCheck, node)) {
    				int flow = getEdgeFlow(nextNeighbourToCheck, node);
    				if(flow > 0) {
    					setLabel(nextNeighbourToCheck, node, Math.min(delta, flow));
    				}
    			}
    		}
    		nextNeighbourToCheck++;
    	}
    }
    
    public void upgradeFlow() { //TODO
    	int currentNode = getAmountNodes() - 1;
    	int nextNode = getLabelAtNode(currentNode)[0];
    	int delta = getLabelAtNode(getAmountNodes() - 1)[1];
    	
    	while(currentNode > 0) {
    		if(isGoodEdge(nextNode, currentNode)) {
    			flowAmounts[nextNode][currentNode] += delta;
    		}
    		else {
    			flowAmounts[nextNode][currentNode] -= delta;
    		}
    		currentNode = nextNode;
    		nextNode = getLabelAtNode(currentNode)[0];
    	}
    }
    
   
    
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED