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

## 求数据，dinic死活不过

Posted by zpclinux at 2012-08-13 11:50:19 on Problem 2112
```用ek就过了

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

Followed by: