CE

Flow

Flow Matching

Bottleneck

The task is to find the smallest number of edges to remove to disconnect the source from the sink.
→ find a maxflow = mincut → BFS through the graph to find sets $S,T$ and then output the edges that cross the cut.

Queue<Integer> Q = new ArrayDeque<Integer>();
boolean[] visited = new boolean[n];
Q.add(0); visited[0] = true;
 
// BFS through the Graph to find the boundary
while (Q.size() > 0) {
  int u = Q.remove();
  
  for (int v : GG.get(u)) {
	if (!visited[v] && G.getFlow(u, v) < G.getCapacity(u, v)) {
	  Q.add(v); visited[v] = true;
	}
  }
}
 
// count the edges and their type crossing the set
int removed_s = 0; int removed_d = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
	if (i == j) continue;
	if (visited[i] && !visited[j] && G.getCapacity(i, j) > 0) {
	  if (G.getCapacity(i, j) == 1) removed_d++;
	  else removed_s++;
	}
  }
}

Probability

Optimal Choice DP

Forward DP ??

Expectation DP

Sometimes, you can just use probability DP and then sum over some values to get the expectation. But for some, you need your DP table to represent the expectation itself.

Then your recursion looks something like this:

double[][] E = new double[][];
 
for (...) {
	for (...) {
		E[i][j] = 1.0
		if (...) E[i][j] += pr[i]*E[i][j+1];
	}
}

For this to work, whatever you are counting must be monotone increasing, and you to top to bottom!

Also make sure that the expectation for the final row is 0 → you’re already done, no more.