拆点、最小割的模板题。
我只想说一点。拆点时不可以下意识地初始化！起点和终点不能直接写编号！写拆点后的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;
}