[ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃

【定義】

給你兩個數組，$benefit[i]$表示選$i$的利潤、$cost[i]$表示選$i$的花費。
如果選$i$，定義$x[i]=1$否則$x[i]=0$，通常題目會給你選擇的限制條件，像是必須是一顆生成樹之類的，這裡就把它忽略掉
我們的目標是要求$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}$的最大值。

【分析】

先不管最大化問題，令$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}=L$
可以把式子改寫成$(\sum{benefit[i] \times x[i]})-L \times (\sum{cost[i] \times x[i]})=0$
分離參數得到$\sum{(benefit[i]-L \times  cost[i]) \times x[i]}=0$
只要知道$L$，$(benefit[i]-L \times  cost[i])$是直接可以求出來的，先記他為$d(i,L)$吧
那可以設$f(L)=\sum{d(i,L) \times x[i]}$

我們的目標變成是要最大化$L$
那若存在一種$x$的選法使得$f(L)>0$能夠證明什麼呢?
$f(L)>0 \to \frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}>L$那表示存在另一個$L$會比現在的$L$還要好
那 $f(L)<0$?很明顯這種情況完全沒有意義，因為找不到這種$L$

最佳的$L$會讓所有$x$的選法都$f(L)\leq0$，只要找到這樣的$L$就說明他是最佳解了
也可以用類似的想法求最小化$L$，這裡就不贅述了。

【解法】

根據剛剛找出來的性質$f(L)$是單調性的，我們可以二分搜$L$，然後驗證是否存在一組解使得$f(L)>0$，這很簡單就不附code了。
另一個有效率的算法是Dinkelbach，他跟二分搜不一樣的地方是他要去求解，在驗證解跟求解的複雜度一樣的時候Dinkelbach是會比較快的，但有時候求解的複雜度會比驗證解的複雜度還要高，因此要看情況使用
以下附上虛擬碼：

	Dinkelbach(){
	L=任意狀態(通常設為0);
	do{
	Ans=L;
	for(i:所有元素)d[i]=benefit[i]-L*cost[i];//計算d值
	找出一組使f(L)最大的x;
	p=0,q=0;
	for(i:所有元素){
	if(x[i])p+=benefit[i],q+=cost[i];
	}
	L=p/q;//更新解，注意q=0的情況
	}while(abs(Ans-L)>EPS);
	return Ans;
	}

view raw Dinkelbach.cpp hosted with ❤ by GitHub

常見的題型有：最優比率環、最優比率生成樹、最大密度子圖(有flow解)等

[ dominator tree ] 有向圖的支配樹

dominator tree，中文名稱叫支配樹
給一張有向圖$G$，我們從其中一個點$r$出發到$y$的所有路徑中，一定會經過點$x$，就稱$x$是$y$的必經點；我們把距離$y$最近的必經點稱為最近必經點，記為$idom(y)$。
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$，那對於一個點$y$，$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。
注意code裡的$idom$跟我定義的不一樣
我是看這份講義的偽代碼寫出來的：

	struct dominator_tree{
	static const int MAXN=5005;
	int n;// 1-base
	vector<int> G[MAXN],rG[MAXN];//存圖和反向圖
	int pa[MAXN],dfn[MAXN],id[MAXN],dfnCnt;
	int semi[MAXN],idom[MAXN],best[MAXN];
	vector<int> tree[MAXN];//dominator_tree存這裡
	void init(int _n){
	n=_n;
	for(int i=1;i<=n;++i)G[i].clear(),rG[i].clear();
	}
	void add_edge(int u,int v){
	G[u].push_back(v);
	rG[v].push_back(u);
	}
	void dfs(int u){
	id[dfn[u]=++dfnCnt]=u;
	for(auto v:G[u]) if(!dfn[v]){
	dfs(v),pa[dfn[v]]=dfn[u];
	}
	}
	int find(int y,int x){
	if(y<=x)return y;
	int tmp=find(pa[y],x);
	if(semi[best[y]]>semi[best[pa[y]]])
	best[y]=best[pa[y]];
	return pa[y]=tmp;
	}
	void tarjan(int root){
	dfnCnt=0;
	for(int i=1;i<=n;++i){
	dfn[i]=idom[i]=0;
	tree[i].clear();
	best[i]=semi[i]=i;
	}
	dfs(root);
	for(int i=dfnCnt;i>1;--i){
	int u=id[i];
	for(auto v:rG[u]) if(v=dfn[v]){
	find(v,i);
	semi[i]=min(semi[i],semi[best[v]]);
	}
	tree[semi[i]].push_back(i);
	for(auto v:tree[pa[i]]){
	find(v,pa[i]);
	idom[v] = semi[best[v]]==pa[i] ? pa[i] : best[v];
	}
	tree[pa[i]].clear();
	}
	for(int i=2; i<=dfnCnt; ++i){
	if(idom[i]!=semi[i]) idom[i]=idom[idom[i]];
	tree[id[idom[i]]].push_back(id[i]);
	}
	}
	};

view raw dominator_tree.cpp hosted with ❤ by GitHub