Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:找到错了！！

Posted by zpclinux at 2012-08-13 13:08:37 on Problem 2112
In Reply To:求数据，dinic死活不过 Posted by:zpclinux at 2012-08-13 11:50:19
```> 用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;
> }

1 2 5
2 3 3
2 4 4
3 5 3
4 5 4

Followed by: