\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年8月5日 星期五

[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\),定義:
\(w_v(u)\)為點\(u\)的權重,\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重,\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和,\(u,v \in V\)

重心的定義是:
以這個點為根,那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)

\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)


 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下,就是一般的樹重心

性質:
  1. 把兩個樹通過一條邊相連得到一個新的樹,那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
  2. 把一個樹添加或刪除一個葉子,那麼它的重心最多只移動一條邊的距離。
用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點,即為樹重心
樹重心求法(用vector存無向樹):

[ bipartite graph multiple matching ] 二分圖多重匹配增廣路算法

這種問題的題目通常是這樣:

給一張圖G有n1個點和n2個點,n1個點之間沒有邊,n2個點之間也沒有邊,但是n1和n2個點之間有m條邊(簡單的來說就是n1個點和n2個點的二分圖啦),沒有重邊;其中n2個點每個點\(u\)都有一個可接受匹配數 \(c_u\)。
n1的點只能跟一個點匹配,但n2的點在不超過可接受匹配數的情況下,可以跟多個點匹配,求這張圖的最大匹配

通常可以利用拆點的方法或是flow來做,但是這樣空間跟效率都不是很好,這裡提供一個有效率的方法:

複雜度分析:
設n2個點每個點\(u\)都有一個值\(E_u\)表示和\(u\)相鄰的邊數,則總複雜度為
$$ \ord{n1*(\sum{c_u*E_u}+n1+n2)} $$