//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "网络流-最大流与最小割": {
        "prefix": "acm-3.5wangluoliu",
        "body": [
            "struct Edge {",
            "    int to, rev;",
            "    int cap;",
            "    bool is_cut; // 标记是否为割边",
            "};",
            "",
            "class MinCut {",
            "private:",
            "    std::vector<Edge> G[MAXN];",
            "    int level[MAXN];",
            "    int iter[MAXN];",
            "",
            "public:",
            "    // 添加一条从from到to，容量为cap的边",
            "    void addEdge(int from, int to, int cap) {",
            "        G[from].push_back({to, (int)G[to].size(), cap, false});",
            "        G[to].push_back({from, (int)G[from].size() - 1, 0, false});",
            "    }",
            "",
            "    // 构建层次图",
            "    bool bfs(int s, int t) {",
            "        memset(level, -1, sizeof(level));",
            "        std::queue<int> q;",
            "        level[s] = 0;",
            "        q.push(s);",
            "        while (!q.empty()) {",
            "            int v = q.front(); q.pop();",
            "            for (const auto& e : G[v]) {",
            "                if (e.cap > 0 && level[e.to] < 0) {",
            "                    level[e.to] = level[v] + 1;",
            "                    q.push(e.to);",
            "                }",
            "            }",
            "        }",
            "        return level[t] != -1;",
            "    }",
            "",
            "    // 在层次图上寻找增广路",
            "    int dfs(int v, int t, int upTo) {",
            "        if (v == t) return upTo;",
            "        for (int &i = iter[v]; i < G[v].size(); ++i) {",
            "            Edge &e = G[v][i];",
            "            if (e.cap > 0 && level[v] < level[e.to]) {",
            "                int d = dfs(e.to, t, std::min(upTo, e.cap));",
            "                if (d > 0) {",
            "                    e.cap -= d;",
            "                    G[e.to][e.rev].cap += d;",
            "                    return d;",
            "                }",
            "            }",
            "        }",
            "        return 0;",
            "    }",
            "",
            "    // 求最大流",
            "    int maxFlow(int s, int t) {",
            "        int flow = 0;",
            "        while (bfs(s, t)) {",
            "            memset(iter, 0, sizeof(iter));",
            "            int f;",
            "            while ((f = dfs(s, t, INF)) > 0) {",
            "                flow += f;",
            "            }",
            "        }",
            "        return flow;",
            "    }",
            "",
            "    // 获取最小割的割边集合",
            "    std::vector<std::pair<int, int>> getMinCutEdges(int s) {",
            "        std::vector<std::pair<int, int>> cutEdges;",
            "        bool vis[MAXN] = {0};",
            "        std::queue<int> q;",
            "        q.push(s);",
            "        vis[s] = true;",
            "        while (!q.empty()) {",
            "            int v = q.front(); q.pop();",
            "            for (const auto& e : G[v]) {",
            "                if (e.cap > 0 && !vis[e.to]) {",
            "                    vis[e.to] = true;",
            "                    q.push(e.to);",
            "                }",
            "            }",
            "        }",
            "        // 割边：从S集合到T集合的满流边",
            "        for (int u = 0; u < MAXN; ++u) {",
            "            if (vis[u]) {",
            "                for (const auto& e : G[u]) {",
            "                    if (!vis[e.to] && G[e.to][e.rev].cap > 0) {",
            "                        cutEdges.emplace_back(u, e.to);",
            "                    }",
            "                }",
            "            }",
            "        }",
            "        return cutEdges;",
            "    }",
            "",
            "    // 清空图",
            "    void clear(int n) {",
            "        for (int i = 0; i <= n; ++i) G[i].clear();",
            "    }",
            "};"
        ],
        "description": "插入 网络流-最大流与最小割"
    }
}