Untitled

package sol6;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class solution6 {
	static ArrayList<Edge> edgeList; 
	static ArrayList<ArrayList<Edge>> Gf;
	static int N,M,C,P;
	static int[] removeEdges;
	
	public static class Edge{
		public int from, to, RESCAP;
		public final int CAPACITY;
		public Edge residual;
		public boolean ACTIVATED;
		
		public Edge(int from, int to, int cap) {
			this.from = from;
			this.to = to;
			this.CAPACITY = cap;
			this.RESCAP = cap;
			this.ACTIVATED = true;
		}
		public int getRC() {
			return ACTIVATED ? RESCAP : 0;
		}
		
	}
	public static void main(String[] args) throws FileNotFoundException {
		formatter();
		int nbrOfNodes = 0;
		int p;
		for(int i = 0; i < removeEdges.length; i++) { //Deactivate all edges in removeEdges. Can be all edges.
			p = removeEdges[i];
			edgeList.get(p).ACTIVATED = false;
			edgeList.get(p).residual.ACTIVATED = false;
		}
		int flow = Ford_Fulkerson(0, N-1, Gf); //Perform first Ford Fulkerson method
		Edge m;
		for(int i = removeEdges.length-1; i >= 0 && flow < C; i--) { //So least-activated graph is alredy in place 
				m = edgeList.get(removeEdges[i]);					// and we just Activate from the end of removeEdges-list.
				m.ACTIVATED = true;							// KEY INSIGHT: Activating another edge can only increase or add nothing to the flow.
				m.residual.ACTIVATED = true;				// CONVERSELY: Deactivatning another edge may only decrease or add nothing to the flow
			flow += Ford_Fulkerson(0, N-1, Gf);
			nbrOfNodes += 1; 								//This is dependent on the order of P in reverse order.
		}
		System.out.println(removeEdges.length - nbrOfNodes + " " + flow); 
	}
	
public static void formatter() throws FileNotFoundException {
	//File input = new File("C:/Users/Carl/Programmering/EDAF05-labs-public/6railwayplanning/data/secret/4huge.in");
	Scanner scan = new Scanner(System.in);
	String[] first = scan.nextLine().split(" ");
	N = Integer.parseInt(first[0]);
	M = Integer.parseInt(first[1]);
	C = Integer.parseInt(first[2]);
	P = Integer.parseInt(first[3]);
	int from, to, cap;
	edgeList = new ArrayList<>();	
	Gf = new ArrayList<>();
	for(int i =0; i < N; i++){Gf.add(new ArrayList<Edge>());}
	
	for (int i = 0; i < M; i++) {
		String[] line = scan.nextLine().split(" ");
		from = Integer.parseInt(line[0]);
		to = Integer.parseInt(line[1]);
		cap = Integer.parseInt(line[2]);
		Edge m1 = new Edge(from, to, cap);
		Edge m2 = new Edge(to, from, cap);
		m1.residual = m2;
		m2.residual = m1;
		edgeList.add(m1);
		Gf.get(from).add(m1);
		Gf.get(to).add(m2);
	}
	removeEdges = new int[P];
	for (int i =0; i < P; i++){removeEdges[i] = Integer.parseInt(scan.nextLine());}
}

public static HashMap<Integer, Edge> BFS(int s, int t, ArrayList<ArrayList<Edge>> graph){ //BFS according to course literature...
	int V = graph.size();
	int v,w;
	boolean[] visited = new boolean[V];
	LinkedList<Integer> q = new LinkedList<>();
	visited[s] = true;
	HashMap<Integer, Edge> pred = new HashMap<>();
	q.add(s); 
	while(q.size() != 0) {
		v = q.poll();
		for (Edge m : graph.get(v)) {
			w = m.to;
			if(visited[w] == false && m.getRC() > 0) { //i.e to is not visited and the edge is activated
				if (w == t) {
					pred.put(w, m); return pred;
					}
				q.add(w);
				pred.put(w,m);
				visited[w] = true;
			}
		}
	}
	return new HashMap<Integer, Edge>();	//If no path was found then return empty HashMap
}


public static int augment(int t, HashMap<Integer, Edge> pred) { 
	int flow = Integer.MAX_VALUE;
	int w = t; 
	Edge m;
	while(!Objects.isNull(pred.get(w))) { //Hitta delta
		m = pred.get(w);
		flow = Math.min(flow, m.getRC());
		w = m.from;
	}
	w = t;
	while(!Objects.isNull(pred.get(w))) { // Updatera pred och rescap
		m = pred.get(w);
		m.RESCAP -= flow;				// = c_e - f_e , forward edge
		m.residual.RESCAP += flow;		// = f_e , backward edge
		w = m.from;						// traverse backwards
	}
	return flow;
}



public static int Ford_Fulkerson(int s, int t, ArrayList<ArrayList<Edge>> Gf) { //*Edmond-Karp's
	//temp = BFS(s,t, Gf);
	HashMap<Integer, Edge> pred = BFS(s,t,Gf); //Find path with bfs
	int currentMaximum = 0;
	while(!pred.isEmpty()) {
		currentMaximum += augment(t, pred); 
		pred = BFS(s,t,Gf);
	}
	return currentMaximum;
}

}