作为一个【NOIP+,省选-】算法,这个算法真的很暴力。同样是最大流,跑得比EK不知快到哪里去了。首先是一个
广度优先搜索(){ 按照可用路径上节点的访问顺序标号。 然后判断一下能否到汇点。 如果不能(汇点没有被标号),那么返回不行。 否则返回行。}然后,只要能找到到汇点的路,就进行一个深度优先搜索(当前到的那个节点了,现在的最大流){ 维护一个当前用过的流量 = 0。 对于它的每条连接儿子节点的边: 如果这个儿子被编的号是它的号加一: 那么最大流就变成了min(儿子能流的流量,当前的流量)。 当然,当前的流量要继续深搜。 儿子的入边减去最大流。 儿子的出边加上最大流。 当前用过的流量加上最大流。 如果当前用过的流量等于最大流的话: 就返回当前用过的流量 如果当前用过的流量是0的话 就把当前节点的值设为-1(不走了) 否则 就返回当前用过的流量。} 算法主体() { 只要还能广度优先搜索: 答案就加上深度优先搜索(源点,正无穷)。 }输出答案就好啦!
bool bfs(){ std::queue q; q.push(S); std::memset(pre, 0, sizeof pre); while (!q.empty()) { int x = q.front(); q.pop(); for (int t = head[x]; t; t = next[t]) if (!pre[lis[t]] && v[t]) { pre[lis[t]] = pre[x] + 1; q.push(lis[t]); } } if (!pre[T]) return false; return true;}int dfs(int pos, int flow){ if (pos == T) return flow; int w, t, used = 0; for (int t = head[pos]; t; t = next[t]) { if (v[t] && pre[lis[t]] == pre[pos] + 1) { w = Dinic(lis[t], std::min(flow - used, v[t])); used += w; v[t] -= w; v[t + 1] += w; if (used == flow) return flow; } } if (!used) pre[pos] = -1; return used;}void Dinic(){ while (bfs()) ans += dfs(S, INT_MAX);}