> 用ek就过了
> 我的dinic，求指点错误：
> int bfs(int s, int t, int start, int end)
> {
> 	int front, rear, q[NN*3];
> 	int u, v;
> 	memset(level, 0, sizeof(level));
> 	front = rear = 0;
> 	level[s] = 1;
> 	q[rear++] = s;
> 	while (front < rear) {
> 		u = q[front++];
> 		if (u == t) return 1;
> 		for (v = start; v <= end; v++) {
> 			if (map[u][v] && !level[v]) {
> 				q[rear++] = v;
> 				level[v] = level[u] + 1;
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> int dfs(int s, int t, int start, int end, int tf)
> {
> 	int u, v, dt, maxFlow = 0;
> 	u = s;
> 	if (u == t) return tf;
> 	for (v = start; v <= end; v++) {
> 		if (map[u][v] != 0 && map[u][v] < INF && level[v] == level[u] + 1) {
> 			dt = dfs(v, t, start, end, MIN(map[u][v], tf));
> 			map[u][v] -= dt;
> 			map[v][u] += dt;
> 			maxFlow += dt;
> 			if (dt == tf) return maxFlow;
> 		}
> 	}
> 	return maxFlow;
> }
> 
> int dinic(int s, int t, int start, int end)
> {
> 	int maxflow = 0;
> 	while (bfs(s, t, start, end)) {
> 		maxflow += dfs(s, t, start, end, INF);
> 	}
> 	return maxflow;
> }


在dfs中maxFlow+=dt;后边还要加上tf-=dt;
这里因为在一层向下扩展时，找到一条路后计算出该路的dt而此层的向下扩展并未结束，因为for循环还可能找到其它的路，这样tf变量记录的可行流就必须得减去已经增广的值 tf-=dt。否则将出现给定的流小于搜索到的可以增广的值。
举个例子： 5个结点5条边的一个图, 1号源点，5号汇点
1 2 5
2 3 3
2 4 4
3 5 3
4 5 4
对这个图来说，假如不进行tf-=dt最终得到的流将是7,即由2到3到5的3 和 2到4到5的4 加一起为7
但事实上由1到2给的流量才只有5.

可气的是我的这个dinic写法交到ditch那道题上却被ac了。。害死人了