拆点、最小割的模板题。
我只想说一点。拆点时不可以下意识地初始化!起点和终点不能直接写编号!写拆点后的Id!
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define In(x) (x) * 2 - 1 #define Out(x) (x) * 2 const int MAX_NODE = 210, MAX_EDGE = 210 * 210 * 2, INF = 0x3f3f3f3f; struct Dinic { private: struct Node; struct Edge; struct Node { Edge *Head, *DfsFrom; int Level; }_nodes[MAX_NODE], *Start, *Target; int TotNode; struct Edge { Node *To; Edge *Next, *Rev; int Cap; }_edges[MAX_EDGE]; int _eCount; Edge *AddEdge(Node *from, Node *to, int cap) { Edge *e = _edges + ++_eCount; e->To = to; e->Cap = cap; e->Next = from->Head; from->Head = e; return e; } bool Bfs() { for (int i = 1; i <= TotNode; i++) _nodes[i].Level = 0; Start->Level = 1; static queue<Node*> q; q.push(Start); while (!q.empty()) { Node *cur = q.front(); q.pop(); for (Edge *e = cur->Head; e; e = e->Next) { if (e->Cap && !e->To->Level) { e->To->Level = cur->Level + 1; q.push(e->To); } } } return Target->Level; } int Dfs(Node *cur, int limit) { if (cur == Target) return limit; if (limit == 0) return 0; int curTake = 0; for (Edge *e = cur->DfsFrom; e; e = (cur->DfsFrom) = e->Next) { if (e->Cap && e->To->Level == cur->Level + 1) { int nextTake = Dfs(e->To, min(limit - curTake, e->Cap)); curTake += nextTake; e->Cap -= nextTake; e->Rev->Cap += nextTake; } if (curTake == limit) break; } return curTake; } public: void Init(int n, int s, int t) { TotNode = n; Start = _nodes + s; Target = _nodes + t; } void Build(int uId, int vId, int cap) { Node *u = _nodes + uId, *v = _nodes + vId; Edge *e1 = AddEdge(u, v, cap), *e2 = AddEdge(v, u, 0); e1->Rev = e2; e2->Rev = e1; } int MaxFlow() { int ans = 0; while (Bfs()) { for (int i = 1; i <= TotNode; i++) _nodes[i].DfsFrom = _nodes[i].Head; ans += Dfs(Start, INF); } return ans; } }g; int main() { int totNode, totEdge, s, t; scanf("%d%d%d%d", &totNode, &totEdge, &s, &t); g.Init(totNode * 2, Out(s), In(t));//!!!!!!!!!!!!!!!!!!!!!!!!!! for (int i = 1; i <= totNode; i++) g.Build(In(i), Out(i), 1); for (int i = 1; i <= totEdge; i++) { int u, v; scanf("%d%d", &u, &v); g.Build(Out(u), In(v), INF); g.Build(Out(v), In(u), INF); } printf("%d\n", g.MaxFlow()); return 0; }