[ 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存無向樹):

	#define MAXN 100005
	#define INF 0x3f3f3f3f
	int n;
	vector<int> g[MAXN];
	int size[MAXN];
	int ans,balance_size;
	inline void init(){
	for(int i=0;i<n;++i)g[i].clear();
	balance_size=INF;
	}
	void dfs(int u,int pa){
	size[u]=1;
	int max_son_size=0;
	for(size_t i=0;i<g[u].size();++i){
	int v=g[u][i];
	if(v!=pa){
	dfs(v,u);
	size[u]+=size[v];
	max_son_size=max(max_son_size,size[v]);
	}
	}
	max_son_size=max(max_son_size,n-size[u]);
	if(max_son_size<balance_size||/*找編號最小*/(max_son_size==balance_size&&u<ans)){
	ans=u;
	balance_size=max_son_size;
	}
	}
	inline int tree_centroid(){
	dfs(0,-1);
	return ans;
	}

view raw tree_centroid.cpp hosted with ❤ by GitHub

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

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

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

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

	#define MAXN1 1005
	#define MAXN2 505
	int n1,n2;//n1個點連向n2個點，其中n2個點可以匹配很多邊
	vector<int > g[MAXN1];//圖
	int c[MAXN2];//每個屬於n2點最多可以接受幾條匹配邊
	vector<int> match_list[MAXN2];//每個屬於n2的點匹配了那些點
	bool vis[MAXN2];//是否走訪過
	bool dfs(int u){
	for(size_t i=0;i<g[u].size();++i){
	int v=g[u][i];
	if(vis[v])continue;
	vis[v]=true;
	if((int)match_list[v].size()<c[v]){
	match_list[v].push_back(u);
	return true;
	}else{
	for(size_t j=0;j<match_list[v].size();++j){
	int next_u=match_list[v][j];
	if(dfs(next_u)){
	match_list[v][j]=u;
	return true;
	}
	}
	}
	}
	return false;
	}
	inline int max_match(){
	for(int i=0;i<n2;++i)match_list[i].clear();
	int cnt=0;
	for(int u=0;u<n1;++u){
	memset(vis,0,sizeof(bool)*n2);
	if(dfs(u))++cnt;
	}
	return cnt;
	}

view raw Augmenting Path multiple.cpp hosted with ❤ by GitHub

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