Modify a small un-necessary code of dinic. "i=f||!e[i].cap?e[i].nxt:i". This is necessary on SAP or Highest Relabel since when the current edge reach to end, it will be relabeled. There's a condition that the previous flow is used up and the current edge is also used up, in this situation, the vertice will be relabeled instead of the next time. Since dinic has no need to relable, this '!e[i].cap' in not necessary.
HDU 1565 - Fang Ge Qu Shu (1)
Problem : n*n grids with each grid has a value. Choose some of them s.t. no neighbour can be chosen at the same time. Find the way s.t. the sum of chosen number is maximum.
Solution : For grid (i, j) if i+j is odd, connect source to it with capacity a[i][j], otherwise connect it to sink with capacity a[i][j]. For each vertice source connect to, connect it to its neighbour with INF capacity. The maximum flow from source to sink (the minimum cut to cut s->t) is the smallest value should be cut.
Proof :
If an edge, with an endpoint either source or sink, of transformed graph is cut, the correspond grid in original problem is abandoned. With this perspective, the valid chosen has one-to-one reflection to a s-t cut.
1) Grid u and v are neibourhood if and only if in transformed graph, u and v aren't both connect to source or sink, and there is an edge connect from former to latter.

2)
-> : If the chosen is invalid, a neighour u and v is chosen at the same time. In transformed graph, one must connect with source, and the other connect with sink, both not be cut. At the same time, u and v must connected. Thus there is a path from source to sink.
<- : If there is a path from source to sink, the path must be s->u->v->t, since the graph is a DAG. Hence u and v must be neighbourhood and they're both not abandoned at the same time. Thus the chosen strategy is invalid.
[]