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++) {
		p = removeEdges[i];
		edgeList.get(p).ACTIVATED = false;
		edgeList.get(p).residual.ACTIVATED = false;
	}
	int flow = Ford_Fulkerson(0, N-1, Gf);
	Edge m;
	for(int i = removeEdges.length-1; i >= 0 && flow < C; i--) {
			m = edgeList.get(removeEdges[i]);
			m.ACTIVATED = true;
			m.residual.ACTIVATED = true;
		flow += Ford_Fulkerson(0, N-1, Gf);
		nbrOfNodes += 1;
	}
	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/sample/1.in");
	Scanner scan = new Scanner(input);
	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); //Testar köra direkt residual-angivelse
		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){
	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] && m.getRC() > 0) {
				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 --> 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))) {
		m = pred.get(w);
		flow = Math.min(flow, m.getRC());
		w = m.from;
	}
	w = t;
	while(!Objects.isNull(pred.get(w))) {
		m = pred.get(w);
		m.RESCAP -= flow;
		m.residual.RESCAP += flow;
		w = m.from;
	}
	return flow;
}



public static int Ford_Fulkerson(int s, int t, ArrayList<ArrayList<Edge>> Gf) {
	//temp = BFS(s,t, Gf);
	HashMap<Integer, Edge> pred = BFS(s,t, Gf);
	int currentMaximum = 0;
	while(!pred.isEmpty()) {
		currentMaximum += augment(t, pred);
		pred = BFS(s,t, Gf);
	}
	return currentMaximum;
}

}