求出最大流后构造割集

本文主要是介绍求出最大流后构造割集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求出最大流后构造割集

几个最大流算法构造割集的方法
一些需要构造割集的题目
- hdu3251 Being a Hero
- UVA - 11248 Frequency Hopping

按照割集的定义，需要将结点分成S、T两个集合，那些一端在S另一端在T的边才是割。不能主观认为满流边就都是割，因为割边一定满流，但部分满流边并不是割。

几个最大流算法构造割集的方法

Edmonds–Karp算法：算法结束时，a[u]>0的结点集合为S，其他结点集合为T。
Dinic算法：算法结束时，vis[u]为true的结点集合为S，其他结点集合为T。
ISAP算法：算法结束后，还要再调用一次bfs，vis[u]为false的结点集合为S，其他结点集合为T。

一些需要构造割集的题目

hdu3251 Being a Hero

UVA - 11248 Frequency Hopping

UVA - 11248 Frequency Hopping
本题非常经典，除了需要构造割集外，还需要两个重要优化：第一个优化是求完最大流以后每次在其残量网络基础上增广，第二个优化是每次没必要求出最大流，增广到流量至少为C时就可以结束。
AC代码：

#include <iostream>
#include <cstring>
#include <set>
using namespace std;#define INF 2147483647
#define M 10010
#define N 102
struct edge {int u, v, cap, flow;} e[M<<1];
int g[N][N<<1], q[N], p[N], d[N], cur[N], num[N], cnt[N], c, n, m, f, kase = 0; bool vis[N], is_t[N];void add_edge(int u, int v, int cap) {e[c].u = u; e[c].v = v; e[c].cap = cap; e[c].flow = 0; g[u][cnt[u]++] = c++;e[c].u = v; e[c].v = u; e[c].cap = 0; e[c].flow = 0; g[v][cnt[v]++] = c++;
}bool bfs(int s, int t) {memset(vis, 0, sizeof(vis)); q[0] = t; d[t] = 0; vis[t] = true;int head = 0, tail = 1;while (head < tail) {int v = q[head++];for (int i=0; i<cnt[v]; ++i) {const edge& ee = e[g[v][i]^1];if (!vis[ee.u] && ee.cap > ee.flow) vis[ee.u] = true, d[ee.u] = d[v] + 1, q[tail++] = ee.u;}}return vis[s];
}int max_flow(int f0 = 0) {int flow = f0, s = 1, t = n;if (!bfs(s, t)) return f0;memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur));for (int i=1; i<=n; ++i) ++num[d[i]];int u = s;while (d[s] < n) {if (u == t) {int a = INF;for (int v=t; v!=s; v = e[p[v]].u) a = min(a, e[p[v]].cap - e[p[v]].flow);for (int v=t; v!=s; v = e[p[v]].u) e[p[v]].flow += a, e[p[v]^1].flow -= a;flow += a; u = s;if (flow >= f) return flow;}int ok = 0;for (int i=cur[u]; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow && d[u] == d[ee.v] + 1) {ok = 1; p[ee.v] = g[u][i]; cur[u] = i; u = ee.v;break;}}if (!ok) {int m = n - 1;for (int i=0; i<cnt[u]; i++) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow) m = min(m, d[ee.v]);}if (--num[d[u]] == 0) break;++num[d[u] = m+1]; cur[u] = 0;if (u != s) u = e[p[u]].u;}}return flow;
}struct node {int u, v;bool operator< (const node& rhs) const {return u<rhs.u || (u==rhs.u && v<rhs.v);}
};void solve() {memset(cnt, c = 0, sizeof(cnt));while (m--) {int u, v, cap; cin >> u >> v >> cap; add_edge(u, v, cap);}cout << "Case " << ++kase << ": ";int f0 = max_flow();if (f0 < f) {bfs(1, n); memcpy(is_t, vis, sizeof(vis)); set<node> s;for (int i=0; i<c; ++i) e[i].cap -= e[i].flow;for (int i=0; i<c; i+=2) if (is_t[e[i].u] != is_t[e[i].v]) {e[i].cap = f;for (int j=0; j<c; ++j) e[j].flow = 0;if (max_flow(f0) >= f) s.insert({e[i].u, e[i].v});e[i].cap = 0;}if (s.size() > 0) {set<node>::iterator it = s.begin();cout << "possible option:(" << it->u << ',' << it->v << ')';while (++it != s.end()) cout << ",(" << it->u << ',' << it->v << ')';cout << endl;} else cout << "not possible" << endl;} else cout << "possible" << endl;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m >> f && n) solve();return 0;
}