復(fù)雜度 O(n
2m)。支持一邊構(gòu)建網(wǎng)絡(luò)，一邊求最大流。每次調(diào)用 flow()，得到當(dāng)前新增的流量。
#include <iostream>
using namespace std;
const int maxn = 500 + 5;
const int maxm = 100000 + 5;
const int maxint = 0x7FFFFFFF;
class network_c
{
public:
void init(int _n, int _s, int _t);
void add_edge(int u, int v, int _c, bool direct);
int flow();
private:
int n, s, t, m, first[maxn];
int c[maxm], f[maxm], p[maxm], next[maxm];
int queue[maxn], pre[maxn], change[maxn], edge[maxn];
};
void network_c::init(int _n,int _s,int _t)
{
n = _n;
s = _s;
t = _t;
m = 0;
for (int i = 1; i <= n; i++)
first[i] = 0;
}
void network_c::add_edge(int u, int v, int _c, bool direct)
{
m++;
c[m] = _c;
f[m] = 0;
p[m] = v;
next[m] = first[u];
first[u] = m;
m++;
c[m] = direct ? 0 : _c;
f[m] = 0;
p[m] = u;
next[m] = first[v];
first[v] = m;
}
int network_c::flow()
{
int answer = 0, op;
while (1)
{
for (int i = 1; i <= n; i++)
pre[i]=0;
pre[s] = s;
int op = 1;
queue[op] = s;
change[s] = maxint;
for (int cl = 1; cl <= op && pre[t] == 0; cl++)
{
int k = queue[cl];
for (int i = first[k]; i != 0; i = next[i])
if (f[i] < c[i] && pre[p[i]] == 0)
{
pre[p[i]] = k;
edge[p[i]] = i;
change[p[i]] = min(change[k], c[i] - f[i]);
queue[++op] = p[i];
}
}
if (pre[t] == 0)
break;
int d = change[t];
answer += d;
for (int k = t; k != s; k = pre[k])
{
f[edge[k]] += d;
f[((edge[k] - 1) ^ 1) + 1] -= d;
}
}
return answer;
}