[AHOI 2014] 支线剧情 : 有源汇上下界最小费用可行流
基础知识储备
请先确保你已经学会了以下内容:
思路解析
首先上下界的最小/最大费用可行流(最大费用流就是把所有边费用取相反数再跑最小费用流)的套路和普通的上下界可行流没有什么区别。无源汇以及有源汇的套路也都是类似的。在加边的时候,注意保存一下基础的费用即可,也就是所有边的流量下界乘以单位费用的总和。在流量上下界取差值的图上跑完的费用加上基础费用即为最小费用。
无源汇的情况下就是新开一对超级源汇点,然后类似普通可行流,根据每个点流入流出情况将一般的节点向超级源汇去连边。有源汇则是在练完所有普通边之后,连接超级源汇点的边之前,还要连接一个原始汇点到原始源点的边,其中流量下界为 $0$ ,上界为 $+\infty$ ,单位费用为 $0$ 。
回到本题,我们构建原始模型。整个模型的源点是 $1$ ,但是没有汇点。但是由于所有的剧情都要看完,我们将除了 $1$ 以外的所有剧情点连接到一个超级汇点 $n+1$ 即可(流量下界为 $0$ ,上界为 $+\infty$ ,单位费用为 $0$)。
然后回到普通的剧情连接上面,每个 $i$ 号节点 连向下一个剧情 $B_{i,j}$ 的时候,加一个流量下界为 $1$ ,上界为 $+\infty$ ,单位费用 $T_{i,j}$ 的边即可。不难理解,因为每个支线剧情路线最多可以走无数次,但是一定要至少走一次。
然后跑有源汇上下界最小费用可行流即可。这里给一个基于网络单纯形的最小费用最大流实现。
using cap = i64;
const int N = 310;
const int M = 10005;
// 1-indexed
namespace MCMF
{
const i64 flow_INF = 1145141919810ll;
const i64 cost_offset = 1145141919;
int n, m, s, t;
struct edge
{
int from, to, nxt;
cap flow, cost;
bool origin;
} e[M << 1];
int cnt;
int h[N];
int add_edge(int u, int v, cap flow, cap cost, bool directed = true)
{
++m;
e[++cnt].from = u, e[cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, e[cnt].cost = cost, e[cnt].origin = 1;
h[u] = cnt;
e[++cnt].from = v, e[cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, e[cnt].cost = -cost, e[cnt].origin = 0;
h[v] = cnt;
return cnt;
}
cap get_remain_flow(int no) { return e[no].flow; }
int tme;
int vis[N], fa[N], fe[N], circle[N], mark[N];
cap pi[N];
void dfs(int u, int fi)
{
fa[u] = e[fi].from, fe[u] = fi;
mark[u] = 1;
for (int i = h[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (e[i].origin && !mark[v])
dfs(v, i);
}
}
cap phi(int u)
{
if (mark[u] == tme)
return pi[u];
mark[u] = tme, pi[u] = phi(fa[u]) + e[fe[u]].cost;
return pi[u];
}
cap pushflow(int eg)
{
int rt = e[eg].from, lca = e[eg].to;
++tme;
int circle_cnt = 0;
while (rt)
mark[rt] = tme, rt = fa[rt];
while (mark[lca] ^ tme)
mark[lca] = tme, lca = fa[lca];
cap minflow = e[eg].flow, p = 2, del_u = 0;
for (int u = e[eg].from; u ^ lca; u = fa[u])
{
circle[++circle_cnt] = fe[u];
if (e[fe[u]].flow < minflow)
minflow = e[fe[u]].flow, del_u = u, p = 0;
}
for (int u = e[eg].to; u ^ lca; u = fa[u])
{
int ne = fe[u] ^ 1;
circle[++circle_cnt] = ne;
if (e[ne].flow < minflow)
minflow = e[ne].flow, del_u = u, p = 1;
}
circle[++circle_cnt] = eg;
cap cost = 0;
for (int i = 1; i <= circle_cnt; ++i)
{
cost += e[circle[i]].cost * minflow;
e[circle[i]].flow -= minflow, e[circle[i] ^ 1].flow += minflow;
}
if (p == 2)
return cost;
int u = e[eg].from, v = e[eg].to;
if (p == 1)
std::swap(u, v);
int last_e = eg ^ p, last_u = v;
while (last_u ^ del_u)
{
last_e ^= 1, --mark[u], std::swap(fe[u], last_e);
int nu = fa[u];
fa[u] = last_u, last_u = u, u = nu;
}
return cost;
}
void init_sz(int _n) { n = _n, m = 0, cnt = 1, tme = 1; }
std::pair<cap, cap> solve(int _s, int _t)
{
s = _s, t = _t;
add_edge(t, s, flow_INF, -cost_offset);
dfs(t, 0), mark[t] = ++tme;
fa[t] = 0;
cap cost = 0, flow = 0;
bool run = 1;
while (run)
{
run = 0;
for (int i = 2; i <= cnt; ++i)
if (e[i].flow && e[i].cost + phi(e[i].from) - phi(e[i].to) < 0)
cost += pushflow(i), run = 1;
}
flow = e[cnt].flow;
return std::make_pair(flow, cost + flow * cost_offset);
}
}
namespace st_bound_MCMF
{
cap fl[N]; // > 0 : supply, < 0 demand
cap supply_sum, base_cost, extra_cost;
cap ori_edge_lo[M];
int rev_edge_no[M];
int t_to_s_no;
int n, s, t, S, T;
void init(int _n, int _s, int _t) { n = _n, s = _s, t = _t, MCMF::init_sz(n + 2), S = n + 1, T = n + 2; }
void standard_supply_or_demand(int no, cap val) { fl[no] += val; }
void add_edge(int no, int u, int v, cap lo, cap hi, cap cost)
{
fl[u] -= lo, fl[v] += lo, ori_edge_lo[no] = lo;
base_cost += lo * cost;
rev_edge_no[no] = MCMF::add_edge(u, v, hi - lo, cost);
}
bool solve()
{
t_to_s_no = MCMF::add_edge(t, s, MCMF::flow_INF, 0);
for (int i = 1; i <= n; ++i)
{
if (fl[i] > 0)
MCMF::add_edge(S, i, fl[i], 0), supply_sum += fl[i];
else if (fl[i] < 0)
MCMF::add_edge(i, T, -fl[i], 0);
}
std::pair<cap, cap> ans = MCMF::solve(S, T);
return extra_cost = ans.second, ans.first == supply_sum;
}
cap mincost() { return base_cost + extra_cost; }
cap get_pi(int u) { return MCMF::cost_offset + MCMF::pi[u]; }
cap real_flow(int no) { return ori_edge_lo[no] + MCMF::get_remain_flow(rev_edge_no[no]); }
}
int main()
{
int n = rd(), S = 1, T = n + 1, edge_cnt = 0;
st_bound_MCMF::init(n + 1, S, T);
for (int i = 1; i <= n; ++i)
{
int K = rd();
while (K--)
{
int b = rd(), t = rd();
st_bound_MCMF::add_edge(++edge_cnt, i, b, 1, MCMF::flow_INF, t);
}
}
for (int i = 2; i <= n; ++i)
st_bound_MCMF::add_edge(++edge_cnt, i, T, 0, MCMF::flow_INF, 0);
st_bound_MCMF::solve();
wr(st_bound_MCMF::mincost());
}