用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;
}

• Re:找到错了！！ (1413) zpclinux 2012-08-13 13:08:37