In mathematics you don't understand things, you just get used to them.

1. Introduction

   Define a closure of a directed graph $G=(V,E)$ as an induced set of vertexes of $G$, where the out-tended edges in $E$ start at some vertex in the closure of $G$ and end at some vertex in the closure, too. More formally, closure is defined as a set of vertexes $V'\subseteq V$, such that $\forall u\in V',s.t.\forall\left<u,v\right>\in E,v\in V'$.

   For the Maximum Weight Closure of a Graph, we define it as, with starting out endowing vertexes in $V'$ costs called $w_u$, the maximum value of $\sum\limits_{u\in V'}w_u$.

2. Construction of Algorithm

   Add a source $s$ and a sink $t$ to the original graph, endow the origin edges in $E$ with capacities that $+\infty$, and connect $s$ with points with positive costs with the points' costs as capacities on them while $t$ connects to those with negative costs with the minus points' costs as capacities on them, where $+\infty$ is defined as any number greater or equal to $\sum |w_i|$.

   More formally, as explained & illustrated:

$$ V_N=V\cup\{s,t\} \\ E_N=E\cup\left\{\left<s,v\right>\mid v\in V,w_v\geqslant0\right\}\cup\left\{\left<v,t\right>\mid v\in V,w_v<0\right\} \\ \begin{cases} c(u,v)=+\infty,\left<u,v\right>\in E \\ \displaystyle c(s,v)=w_v,w_v\geqslant0 \\ \displaystyle c(v,t)=-w_v,w_v<0 \end{cases} $$

   Which make it easy to understand the answer would be $\text{min-cut}(G_N=\{V_N,E_N\})$.


[1] Referenced to 最小割模型在信息学竞赛中的应用 by 胡伯涛 Amber.

flows

「luogu - P3158」「cqoi 2011」放棋子
上一篇 «
Dinic Algorithm Implementation with Huge Constant, and What is Behind It
» 下一篇