編程兔暑假3.5階段集訓Day6——狀壓(狀態壓縮)dp、dp優化以及圖論

来源:https://www.cnblogs.com/YZYc/archive/2022/07/30/Summer-Code-Day5Part2-Day6Part1-Class-YPPAH.html
-Advertisement-
Play Games

今天我們先來講一下狀態壓縮dp(也稱狀壓dp)。狀壓dp,顧名思義,就是把狀態壓縮起來。比如對於8*8 的棋盤,每個位置可以放一個棋子,對於在第i行第2個位置和第6個位置放了棋子,我們可能需要8維或9維數組表示。因此我們就有了把一行狀態壓縮成一個數字的做法。一般我們會轉化為二進位,如果每個位置可以有 ...


        今天我們先來講一下狀態壓縮dp(也稱狀壓dp)。狀壓dp,顧名思義,就是把狀態壓縮起來。比如對於8*8 的棋盤,每個位置可以放一個棋子,對於在第i行第2個位置和第6個位置放了棋子,我們可能需要8維或9維數組表示。因此我們就有了把一行狀態壓縮成一個數字的做法。一般我們會轉化為二進位,如果每個位置可以有3種狀態,那我們可以採用三進位。這樣只需要一個大小為2^8的一維數組我們就可以存下所有狀態,這就是狀態壓縮。

eg1
• 現在有 n*m 的方格棋盤,和無限的 1*2 的骨牌,問有多少種方法能用骨牌 鋪滿棋盤。
• 1<=n,m<=11.

演算法分析:
首先 n*m 是奇數一定拼不出來。使用狀態壓縮,如果第 i 個位置上放骨牌,就在二進位對應位置填 1,否則是 0. 用 f[i][s] 表示填到了第 i 行狀態是 s 的方案數。答案就是 f[n][(1<<m)-1]。可是怎樣進行狀態的轉移呢?
首先我們的決策有兩種:橫著放或者豎著放。
我們需要連續考慮二行,如果橫著放,需要兩個連續的空位,且上一行這兩個位置也被覆蓋;如果豎著放有2種情況:
    1、上一行位置是空的,我們就可以把空填上。
    2、上一行是覆蓋的,那麼我們把這一行位置設為空,表示下一行必須豎著放 填上這塊空白。

代碼實現:
void dfs(int i,int now,int pre)
{
	if(i>m)
	{
		return ;
	}
	if(i==m)
	{
		++tot;
		from[tot]=pre;
		to[tot]=now;
		return ;
	}
	dfs(i+2,now<<2|3,pre<<2|3);
	dfs(i+1,now<<1,(pre<<1)|1);
	dfs(i+1,now<<1|1,pre<<1);
}

主函數: 
int f[12][1<<11];
dfs(0,0,0);
f[0][(1<<m)-1]=1;
for(int i=0;i<n;i++)
{
	for(int j=1;j<=tot;j++)
	{
		f[i+1][to[j]]+=f[i][from[j]];
	}
}

        通過上面的例題,大家應該對狀壓dp也有了一個簡單的瞭解了,現在我們繼續進行練習:

noip2016D2T3 憤怒的小鳥
有一彈弓位於原點 (0, 0) 處,每次向第一象限發射一隻紅色的小鳥,小鳥飛行軌跡均為形如 y=ax^2+bx 的曲線,其中 a, b 是指定的參數,且 a<0。當小鳥落回地面(x軸)時,它會瞬間消失。
在游戲某個關卡裡,平面第一象限中有 n 只綠色小豬,第 i 只小豬坐標為 (xi, yi)。如果某隻小鳥經過了 (xi, yi),那麼第 i 只小豬就會被消滅掉。比如說兩隻小豬分別位於 (1, 3) 和 (3, 3), 這樣可以選擇一隻飛行軌跡 y=-x^2+4x 的小鳥把兩隻小豬一次給消滅掉。 
問最少需要多少小鳥能消滅掉所有小豬。 小豬總數<=18

演算法分析:
首先我們註意到數據範圍非常小,可以考慮狀壓dp。
 設 f[s] 表示消滅 s 集合中的豬花費的最小步數,在已有 s 集合基礎上,再選擇一條拋物線使它經過 t 集合的點。 那麼就可以用 f[s]+1 去更新 f[s|t]。因為三點確定一條拋物線,且必經過原點。
因此,我們可以枚舉 s 集合外任意兩點,算出經過這兩點的拋物線,然後枚舉所有點看是否落在該拋物線上,從而得到點集 t:f[s|t]=min(f[s|t],f[s]+1)。
而經過點 i 和 j 的拋物線所經過的點集 t[i][j] 可以預處理,時間複雜度O(n^3). 之後 dp 枚舉每個集合,每個集合枚舉兩個點,時間複雜度 O(2^n * n^2)。

然後我們看看預處理的部分:
對於經過點 i 和 j 的拋物線有: a*xi^2 + b*xi = yi a*xj^2 + b*xj = yj. 因此 a = (yi*xj - yj*xi) / (xi^2*xj - xj^2*xi), b=(yi - a*xi^2)/ xi
如果 a>=0,則不符合題意,t[i][j] = 0;否則,枚舉所有點,如果第 k 個點在拋物線上,則 t[i][j] |= (1<<(k-1))

核心代碼:
memset(f,0x3f,sizeof f);
f[0]=0;
for(int s=0;s<(1<<n);s++)
{
	if(f[s]=INF)
	{
		continue;
	}
	for(int i=0;i<n;i++)
	{
		if(!(s>>i&1))
		{
			for(int j=0;j<n;j++)
			{
				if(!(s>>j&1))
				{
					f[s|t[i][j]]=min(f[s|t[i][j]],f[s]+1);
				}
			}
		}
	}
}
cout<<f[(1<<n)-1];

        接下來我們講講dp中的優化。其實dp中的優化有很多很多,老師dp的課件一共有220頁(好家伙),光優化就占了將近100頁,大家就對dp優化種類之多可想而知了。由於時間原因,今天我們講的每個優化方法只會給一個例題進行講解,大家可以自己在網上look一些巨佬們的博客去進行進一步的研究。

        先來看看基礎的dp優化。最長上升子序列(LIS)學過dp的肯定都很熟悉了,我們今天來看看LIS的O(nlogn)演算法。

• 設 d[i] 為以i結尾最長上升子序列長度。
• 註意到如果 a[i] < a[j] 且 d[i] = d[j],那麼對於後續的狀態 k(k > i && k > j)來說 ,i 不會比 j 差(即如果j滿足 a[j] < a[k],那i一定滿足,反之卻不一定),因此,我們只需保留 i 這個狀態,一定不會損失最優解。所以對於相同的 d 值,只需保留最小的 a[i] 即可。
• 設 g[i] 為長度為 i 的子序列末尾的最小值,顯然 g 是單調的, g[1]<=g[2]<=g[3]…
• 隨著 i 值增大,g 也會動態改變。 
• 給定狀態 i,我們可以二分查找 g 中第一個大於等於 a[i] 的下標k,則有:
    • d[i] = k,此時需要更新 g[k] = a[i]

核心代碼:
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++)
{
	int k=lower_bound(g+1,g+n+1,a[i])-g;
	d[i]=k;
	g[k]=a[i];
	ans=max(ans,d[i]);
}
/*
lower_bound函數的意思是從g數組的第一個元素開始(因為從1開始存的,所以第一個 
參數是g+1,指的是第一個元素的位置),一直到第n個元素(第二個參數的意思是該區間
尾元素位置的下一個位置),查找第一個值大於等於(upper_bound函數查的是大於,可以用來求最長不下降子序列)a[i]
的值的元素下標,如果沒有則返回-1(應該是),最後減去g則是把存儲位置轉換成具體的
數值。
*/ 

        有些dp問題也可以用滾動數組來進行優化。比如有一個二維的 dp 數組 f[i][j],在轉移過程中發現 f[i][j] 都是從 f[i-1][j] 轉移過來的,並且在算 f[i][*] 時之前的所有的 f[i-1][*] 已經全部算好。那麼這個時候就可以把第一維的空間“滾動”掉,因為f[i-1][*]更新完f[i][*]後就沒有用了,具體實現可以用兩個數組f和g輪換著更新:

for(int i=1;i<=n;i++)
{
	memcpy(g,f,sizeof f);//上一個狀態的f數組存進g 
	memset(f,0,sizeof f);//初始化f,將f數組清空 
	/*然後再去用g去更新f*/
}

        更一般的情況是我們可以用二維數組f[2][N](即第一維就是原先f和g兩個數組的合併)。接下來是dp問題中矩陣乘法的優化。首先我們先要會矩陣乘法和矩陣快速冪和構造轉移矩陣。對於二維以上的dp,如f[i][j][k],如果它全部由f[i-1]轉移過來,則我們可以構造轉移矩陣來加速,即把f[i]壓縮成一維數組,f[i-1]也壓縮成一維數組,轉移方程就相當於f[i]=f[i-1]*轉移矩陣。比如f[i][t]+=f[i-1][s],那麼轉移矩陣第s行第t列元素就要加1。這樣對於轉移n次的dp,我們只需要計算轉移矩陣的n次冪即可,時間複雜度也可以從O(n)優化為O(logn)。

        然後我們再看看dp問題的首碼數組優化,我們直接用一個例題來進行介紹:

        

【例】bzoj 1705 Telephone Wire
電話線假設在 n(2<=n<=2e5) 根電話桿上,第 i 根電話線高度為 h[i](1<=h[i]<=100).如果兩根電話桿高度不同,則需要花費 c * 電話桿高度差 (1<=c<=100)的費用。你不能行動電話桿,只能按原有順序架設電話線。
現在你可以加高某些電話桿,加高 x 米需要花費 x^2 的代價,要你求處最少花費是多少。

樣例輸入
5 2
2 3 5 1 4
樣例輸出 
15(分別改造為3 3 5 3 4)

首先發現 h[i] 不大,所以可以作為狀態。設 f[i][j] 表示架設到了第 i 根電話桿且其長度為 j 的最小代價。
狀態轉移方程 f[i][j] = min{ f[i-1][k] + c * |j – k| + (j-h[i])^2 },顯然時間複雜度O(NK^2),枚舉 i, j 狀態共 NK 個,瓶頸在於每個狀態需要枚舉決策 K 種高度。
首先 (j-h[i])^2 與 k 無關: f[i][j] = min{ f[i-1][k] + c * |j – k| } + (j-h[i])^2。
然後我們可以分類討論拆掉絕對值: 
    如果 j > k ,則有: f[i][j] = min{ f[i-1][k] – ck } + cj + (j-h[i])^2
    如果 j < k,則有: f[i][j] = min{ f[i-1][k] + ck } - cj + (j-h[i])^2
接著我們發現min函數部分其實就是一個區間最小值(且不會變)。 我們可以預處理該區間最小值,使枚舉 K 的策略降為O(1)。 
如果k<j : 找一個在 j 左邊的值使其最小,我們可以用首碼數組取維護最小值。 同理,如果k>j ,可以用一個尾碼數組維護最小值。
我們可以用 p[i][j] 維護 min{f[i][k] – ck } (k<=j) q[i][j] 維護 min{f[i][k] + ck } (k>=j),方程就變為:
j>=k : f[i][j] = p[i-1][j] + cj + (j-h[i])^2
j<=k : f[i][j] = q[i-1][j] - cj + (j-h[i])^2
這樣每次轉移時O(1),每次迴圈更新一次 p, q 數組即可,時間複雜度為O(nk),第一維 i 也沒用,可以滾動數組優化掉。

核心代碼:
memset(f,0x3f,sizeof f);
for(int i=h[1];i<=100;i++)
{
	f[i]=(i-h[1])*(i-h[1]);
}
for(int i=2;i<=n;i++)
{
	q[i]=INF;
	for(int j=100;j>=1;j--)
	{
		q[j]=min(f[j]+c*j,q[j+1]);
	}
	p[0]=INF;
	for(int j=1;j<=100;j++)
	{
		p[j]=min(p[j-1],f[j]-c*j);
	}
	memset(f,0x3f,sizeof f);
	for(int j=h[i];j<=100;j++)
	{
		f[j]=(j-h[i])*(j-h[i])+min(p[j]+c*j,q[j]-c*j);
	}
}
int ans=INF;
for(int i=1;i<=100;i++)
{
	ans=min(ans,f[i]);
}

        dp問題的基礎優化就講到這裡,接下來我們講講dp問題中關於單調性(即單調棧和單調隊列)的優化。首先介紹一下斜率優化的dp。想要使用斜率優化,需要保證問題中的決策是單調的,然後可以用單調性來快速跳過冗餘的決策。不知道斜率的童鞋們,推薦一個學習數學超級棒的網站:可汗學院(zh.khanacademy.org),裡面的代數課程中有關於斜率詳細的介紹。上個斜率優化的例題:

hdu3507 print article
有一個長度為 n 的正整數序列 A
每次可以連續輸出幾個數,費用是連續輸出的數字和的平方加上常數M。
求把A輸出的最小費用
n<=5e5

樣例輸入:
5 5
5 9 5 7 5
樣例輸出:
230

演算法分析:
這道題很顯然是個線性dp,設sum[i]為首碼和,f[i]表示輸出前i個數的最小費用。
狀態轉移方程:
    f[i] = min{f[j] + (sum[i]-sum[j])^2 + M) (0<j<i)
這樣枚舉j,時間複雜度O(n^2)
    f[i] = min{f[j] + (sum[i]-sum[j])^2 + M) (0<j<i)
但是這樣在碰到某些毒瘤數據點的時候可能就會TLE了(這裡插句題外話,TLE中E不是Error的意思,全稱應該是Time Limit Exceed時間超限),那該怎麼辦呢?
i表示狀態肯定要枚舉的,所以我們再考慮加速選擇j的決策。j一共有i個需要美劇,如果我們能對所有可能的轉移做一個評估,直接從最優位置轉移過來,那剩下的就不用枚舉了。
我們假設 j 取了 x 和 y (且 x>y)這2個值。
如果x比y好,說明:
f[x] + (sum[i] - sum[x])^2 + M < f[y] + (sum[i] - sum[y])^2 + M就可以變成(f[x] + sum[x]^2) - (f[y] + sum[y]^2) < 2sum[i](sum[x] - sum[y])。
又因為sum[x] > sum[y],所以可以把(sum[x]-sum[y])除到左邊,即( (f[x] + sum[x]^2) - (f[y] + sum[y]^2) ) / (sum[x] - sum[y]) < 2sum[i]。
接著我們發現這個式子特別像斜率的形式,所以我們可以把下標i轉化為二維平面上的點,令X=sum[i],Y=f[i]+sum[i]^2.
如果x>y且x比y好,我們有:
(Y(x)-Y(y))÷(X(x)-X(y))<2*sum[i]
令斜率slope(x,y)= (Y[x] - Y(y)) / (X(x) - X(y)) (x>y)
如果slope(x, y) < 2sum[i],那麼x比y優。

考慮3個點k,j,i。
    如果 k < j < i, 又橫坐標單增,所以 k, j, i 在圖上從左到右。 
    若 slope(j, k) > slope(i, j), 那麼 j 可以淘汰。
分類討論:
    如果 slope(i, j) < 2sum[i], 那麼 i 比 j 優;
    如果 slope(i, j) > 2sum[i], 那麼有 slope(j, k) > 2sum[i], 則 k 比 j 優。
因此每一條線段的斜率應該是遞增的,也就是我們只需要用單調隊列維護下一個凸殼即可。(X=sum[i]增加即橫坐 標增加)。
我們要最小化的是 F = min{ f[x] - 2sum[i]sum[x] + sum[x]^2 } ,讓它變成min F = Y - 2sum[i]X =>Y = 2sum[i]X + F,因此在Y軸上的截距越小越好。
也就是我們用一條斜率為 2sum[i] 的直線從下往上,碰到的下凸殼的第一個 點對應的截距就是對應的最優轉移。

設這個點為 i, 上一個點為 p, 下一個點為 s。
顯然有: slope(i, p) < 2sum[i] < slope(s, i)
由於 sum[i] 單增,所以決策具有單調性。 維護一個指針指向每次對應的最優轉移即可。 總的時間複雜度為O(n)

核心代碼:
double slope(int j,int k)
{
	int dy=f[j]+sum[j]*sum[j]-f[k]-sum[k]*sum[k];
	int dx=sum[j]-sum[k];
	if(!dx)
	{
		return (dy>=0)>1e30:-1e30;
	}
	return (double)dy/(double)dx;
}

主函數
for(int i=1;i<=n;i++)
{
	cin>>sum[i];
	sum[i]+=sum[i-1];
}
int h=0,t=1;
q[0]=0;
for(int i=1;i<=n;i++)
{
	while(h+1<t&&slope(q[h+1],q[h])<=2*sum[i])
	{
		h++;
	}
	f[i]=f[q[h]]+m+(sum[i]-sum[q[h]])*(sum[i]-sum[q[h]]);
	while(h+1<t&&slope(i,q[t-1])<=slope(q[t-1],q[t-2]))
	{
		t--;
	}
	q[t++]=i;
}
cout<<f[n]<<endl;

        接下來簡單看一下dp的單調隊列優化。所謂的單調隊列優化dp等也不過是列完轉移方程後然後可以轉化為一個左右端點遞增的區間詢問最值的問題罷了。直接上題目,肥腸簡單,演算法分析可能會不大詳細,大家不懂的可以自行去BDFS:

Eg.最大連續和(一本通1598)
給定長度為n的序列,找出連續長度不超過m的子序列,使得子序列和最大。

輸入樣例:
6 4
1 -3 5 1 -2 3
輸出樣例: 
7

演算法分析(真的很很很粗糙,大家還是找度娘吧):
把首碼和當做值跑單調隊列即可。

核心代碼:
int a[200005],sum[200005],q[200005];
cin>>n>>m;
for(int i=1;i<=n;i++)
{
	cin>>a[i];
	sum[i]=sum[i-1]+a[i];
}
int ans=sum[1];
if(n<=m)
{
	ans=max(ans,sum[n]);
}
int head=1,tail=0;
for(int i=1;i<n;i++)
{
	while(q[head]<i-m+1&&head<=tail)
	{
		head++;
	}
	while(sum[q[tail]]>=sum[i]&&head<=tail)
	{
		tail--;
	}
	q[++tail]=i;
	ans=max(ans,sum[i+1]-sum[q[head]]);
}
cout<<ans;

        然後是最後一種dp問題中的優化:數據結構優化dp。簡單來說(下麵一句是老師上課講的,課件沒有),就是用線段樹或者樹狀數組之類去優化dp問題。上例題:

cf958c3 encryption
給定一個長度為 N 的正整數序列,請你把它分成 K 段,使得每段的和對 P 取模之後相加的總和最小。
N<=5e5,2<=K,P<=100

樣例輸入:
4 3 10
3 4 7 2
樣例輸出:
6

演算法分析:
這道題同樣也是簡單的一個線性dp,用sum[i]表示首碼和,用f[i][j]表示前i個數分成j段得到的最小值。
狀態轉移方程:
f[i][j] = min{ f[k][j-1] + (sum[i] - sum[k])%p } (0<=k<i)
時間複雜度為O(n^2*k)

我們用 sum[i] 表示前 i 個數的和對 P 取模的結果。因為 sum 取值都是 [0, p),這樣區間 [x+1, y] 的和對 P 取模答案分類討論得:
    如果 sum[x] <= sum[y] : 則為 sum[y] - sum[x]
    否則為 sum[y] - sum[x] + P
回到狀態轉移方程:f[i][j] = min{ f[k][j-1] + (sum[i] - sum[k]+P)%P } (0<=k<i)
    如果 sum[k] <= sum[i]: f[i][j] = min{f[k][j-1] - sum[k]} + sum[i].
    否則: f[i][j] = min{f[k][j-1] - sum[k] + P} +sum[i].
所以我們只需要維護 f[k][j-1] - s[k] 和 f[k][j-1] - s[k] + P 這兩類首碼最小值。 然後根據 sum[k] 和 sum[i] 的大小關係對應去查找就行。

先看 min{f[k][j-1] - sum[k]} (0<=k<i). 要滿足 sum[k] <= sum[i] 且 0<=k<i. 我們只需要從小到大枚舉 i,這樣就自然滿足了後者。也就是每次把 k < i 的 (f[k][j-1] - sum[k]) 插入到下標為 sum[k] 的位置上,查詢的時候在下標區間 [0, sum[i]] 上查詢最小值即可。

對於 min{f[k][j-1] - sum[k] + P} (0<=k<i).我們用另一個數據結構把 f[k][j-1] - sum[k] + P 插入到下標為sum[k] 的位置上。查詢時只要在下標區間 [sum[i]+1, P] 上查最小值即可。
單點修改,區間查最小值 => 線段樹或樹狀數組。
時間複雜度 O(NKlogP)

核心代碼:
int bit[2][105][105];
void add(int i,int j,int x,int v)
{
	x++;
	while(x<=P+1)
	{
		bit[i][j][x]=min(bit[i][j][x],v);
		x+=lowbit(x);
	}
}
int ask(int i,int j,int x)
{
	int ans=INF;
	x++l
	while(x>0)
	{
		ans=min(ans,bit[i][j][x]);
		x-=lowbit(x);
	}
	return ans;
}

主函數
n=read(),k=read(),p=read();
for(int i=1;i<=n;i++)
{
	sum[i]=read(),sum[i]=(sum[i-1]+sum[i])%p;
}
memset(bit,0x3f,sizeof bit);
memset(f,0x3f,sizeof f);
add(0,0,0,0);
add(1,0,0,0);
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=min(i,k);j++)
	{
		f[j]=min(ask(0,j-1,sum[i]),ask(1,j-1,p-sum[i]));
	}
	for(int j=1;j<=min(i,k);j++)
	{
		if(f[j]>=INF)
		{
			continue;
		}
		add(0,j,sum[j],f[j]-sum[j]);
		add(1,j,p-sum[j],f[j]-sum[j]+p);
	}
}
cout<<f[k]<<endl;

        終於,dp講完了,兩百多頁PPT,終於講完了(我得省略了將近150頁)。不多說了,再多說我就要肝到明早了,直接進圖論!!!同樣的,關於最短路的知識點在我的博客主頁里也都有,請各位自行查看,本蒟蒻在這裡就不再寫了。先看拓撲排序吧,上介紹:

• 拓撲圖,就是一張有向聯通無環圖,(不知道有向圖的同學現在去BDFS還來得及)
• 拓撲序就是一張有向圖遍歷的點的順序
• 拓撲排序就是考慮這個有向無環連通圖中,有一條邊(x,y),當選了x點之後才能 選y點,那麼在拓撲序中x點一定要在y點之前
• 具體求拓撲序的方法就是每次在圖中找到入度為0的點,加入到隊列中,同時不斷地擴展

        介紹完直接上題:

洛谷 P1113 雜物
有n個任務,每個任務有完成時間,有一些邊(x,y),表示x任務完成之後才能進行y任務,問最後被選的點的時間是多少。
輸入n行,每行前兩個數是點的標號和權值,後面讀入一些數x表示選了x才能選當前點

n<=100000
in:
7
1 5 0
2 2 1 0 
3 3 2 0 
4 6 1 0 
5 1 2 4 0
6 8 2 4 0 
7 4 3 5 6 0
out:
23

演算法分析:
數列A,B,C,D 表示A<B,B<C,C<D。 在這道題中,我們將給你一系列形如A<B的關係,並要求你判斷是否能夠根據這些關係確定 這個數列的順序,是否有矛盾。
判斷第 x 行出現矛盾:
    出現環,即拓撲排序出隊個數小於當前出現的不同字母數。
判斷第 x 行得到關係:
    拓撲排序出隊個數等於總數且最深的點的深度為n。
全走完還不能確定關係則輸出不確定。

        拓撲排序只要理解原理就可以了,具體代碼大家可以自己研究一下。然後看最小生成樹演算法、次小生成樹演算法以及差分約束。最小生成樹演算法今天主要講的是Kruskal演算法,其實兩種演算法我的博客里都專門講過,感覺老師跟我寫的不大一樣,還是淺講一下吧。

cf76A
gift給你 n 個點, m 條邊,(x, y, w1, w2) 表示連接 x, y 的邊有兩個數 w1,w2, 又給你一對數(g,s), 要你求一個生成樹,使得 g*max(w1) + s*max(w2) 最小
n<=200,m<=100000

in:
3 3 
2 1
1 2 10 15
1 2 4 20
1 3 5 1
out:
30

演算法分析:
• 考慮一個暴力,枚舉w1的最大值x,然後把第一維<=x的邊拿出來建第二維的最小生成樹.
• 時間複雜度O(m^2). 
• 但這樣肯定是不行的,那我們該怎麼優化呢(肯定是考慮生成樹演算法)?
• 再考慮一個暴力,枚舉w1的最大值x,然後把第一維<=x的邊拿出來建第二維的最小生成樹
• 那麼把這個暴力改成按照第一維排序,容易發現,隨著第一維的最大值增加, 可選得第二維最小值會不但減少,因此相當於可以不斷加入邊,然後每次刪掉樹上環上第二維最大的邊即可。
• 複雜度是 O(m*n+mlogm)

核心代碼:
struct edge
{
	int x,y,w1,w2;
	bool operator <(const edge t) const
	{
		return w1<t.w1;
	}
}a[N],q[205];
int findf(int x)
{
	return fa[x]==x?x:fa[x]=findf(fa[x]);
}

主函數
sort(a+1,a+n+1);
int ans=INF;
int t=0,s=0;
for(int i=1;i<=m;i++)
{
	q[++t]=a[i];
	s=0;
	for(int j=t-1;j&&q[j+1].w2<q[j].w2)
	{
		swap(q[j],q[j+1]);
	}
	for(int j=1;j<=n;j++)
	{
		fa[j]=j;
	}
	for(int j=1;j<=t&&s<n-1;j++)
	{
		int fx=findf(q[j].x),fy=findf(q[j].y);
		if(fx!=fx)
		{
			fa[fx]=fy;
			q[++s]=q[j];
		}
	}
	if(s==n-1)
	{
		ans=min(ans,g*a[i],w1+s*q[s].w2);
	}
	t=s;
}
cout<<(ans==INF?-1:ans);

        簡單提一嘴,要想判定一個圖是否只有一個最小生成樹,只需要判定權值相等的邊能用和實際用的數量相等即可。接著,我們來看看次小生成樹演算法。說實話,作者在上課之前只是在某谷上看到過次小生成樹的標簽,今天才真正瞭解了次小生成樹。

        怎麼求次小生成樹呢?一種思想是先求出最小生成樹,然後枚舉刪去最小生成樹中的邊,再求最小生成樹,時間複雜度為O(nmlogm)。接下來,我們看看標準的次小生成樹的求法:

註意到次小生成樹一定是最小生成樹進行一次加邊刪邊操作得到的。 即加入非樹邊 (u,v), 然後一定會形成由樹上 u, v 路徑再加上該邊的環。這樣只需要刪除 環中除此邊外的最大邊即形成新的生成樹。然後依次枚舉非樹邊找最小值即可。

具體操作: 
    1、O(n^2)預處理出最小生成樹上任意兩點形成的路徑的最大邊權。
    2、枚舉非樹邊加入並刪邊,更新生成樹權值和 ans=ans+w[u][v]-maxw[u][v]。
    3、求最小權值和。 時間複雜度O(n^2+m)。 更進一步,任意兩點最大邊權可以倍增來維護。時間複雜度O(nlogn+m)。
其實如果再進一步,我們發現剛剛求解的過程求出來的為 “非嚴格” 次小生出樹。 當加的邊和刪的邊權值相等時出現。那怎麼才能求解一個嚴格的次小生成樹呢?正解其實是倍增的思想。
倍增求解時維護一個嚴格次大值,當加的邊和刪的邊權值相等時,刪次大邊即可。
設 max[i][j], max2[i][j] 維護的是 i 到 2^j 祖先的最大值和次大值。更新時從 max[i][j-1], max[fa[i][j-1]][j-1], max2[i][j-1], max2[fa[i][j-1]][j-1] 四個值中選最大和次大值分別更新就可以了。

        次小生成樹就到這裡,老師的課件上也沒有給題目,大家可以去某谷自己搜搜。最短路演算法大家可以去我的主頁,SPFA、Dijkstra、Bellman-Ford、Floyd都有的。差分約束因為本蒟蒻太蒟蒻了,所以明天問問老師再寫吧!!最後說一下,明天我們要考試了,因為對於作者一個六升七的孩紙來說老師說是信奧提高組及以上的知識,所以我們幾個六升七的已經約定好一起爆零了,明天已經放平心態了。。。。。。

 

 

 

 

--------------------------------------------------------------------------------------分割線-----------------------------------------------------------------------------------------

開玩笑噠!!明天一定要加油加油加油!!!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、Python包 python包在開發中十分常見,一般通過導入包含特定功能的python模塊包進行使用。當然,也可以自己創建打包模塊,然後發佈,安裝使用。 1、安裝包 線上安裝包:pip install 包名; 安裝第三方包:python setup.py install (幾乎每個python第 ...
  • 1、Maven 1.1、Maven概念 背景 在一個項目中經常需要手動導入jar包,當需要的jar包數量多的時候,非常難以管理;同時還需要人為去下載各種jar包。同時不同IDE之間,項目結構不一樣,造成遷移性低下,不通用的問題 因此Maven被創造出來解決這個難題 概念 Maven是專門用於管理和構 ...
  • 數組 數組是啥? 數組是幹嘛的? 數組怎麼用? 不管咋樣,先看百科瞭解億下: C++ 數組 —— 菜鳥教程 C++ 支持數組數據結構,它可以存儲一個固定大小的相同類型元素的順序集合。數組是用來存儲一系列數據,但它往往被認為是一系列相同類型的變數。 數組的聲明並不是聲明一個個單獨的變數,比如 numb ...
  • Wing Pro for Mac是一個基於Python編程語言開發的集成開發環境,主要針對學習Python的Mac用戶設計,你可以通過本軟體調試PythonIED的所有功能,內置安裝,定製,設置項目,編輯,搜索,重構等多種功能,您可以選擇在軟體上建立一個新的編輯方案,也可以選擇安裝擴展的IDE腳本到 ...
  • 什麼是Filter實現許可權攔截,比如說我們登陸一個網站,登陸成功後可以訪問其中的內容,退出登陸後就不能再對內容進行訪問,這就用到了我們的Filter實現許可權攔截。 那麼具體是怎麼實現的呢? 原理很簡單,我們可以給已登錄用戶session存放一個用於標記登陸的數據,只需要在過濾器里看能否獲取數據來進行 ...
  • 監聽器種類數不勝數,監聽器最常被應用在GUI中,不過網站中也可以設置監聽器,這裡我們利用sessionListener實現一個網站線上人數統計的監聽來瞭解一下監聽器的使用。 首先建立一個類來實現監聽器OnlineListener.class 1 package com.jms.listener; 2 ...
  • 過濾器是用來過濾瀏覽器中的數據,例如web伺服器受到一些垃圾請求,後臺可以不處理這些請求或者報錯,還可以用來解決亂碼問題等。 過濾器是在伺服器啟動的時候初始化,在伺服器關閉的時候銷毀。 下麵我們用實例來演示: 首先建立一個過濾器類CharacterEncodingFilter.class 1 pac ...
  • 一、什麼是JavaBean? JavaBean 是特殊的 Java 類,使用 Java 語言書寫,並且遵守 JavaBean API 規範。 JavaBean具有以下的特征: 具有無參構造函數; 屬性私有化; 私有化的屬性通過get和set方法提供訪問。 二、JavaBean的作用 一是為了提高代碼 ...
一周排行
    -Advertisement-
    Play Games
  • 在本篇教程中,我們學習瞭如何使用 Taurus.MVC WebMVC 框架創建一個簡單的頁面。 我們創建了一個控制器並編寫了一個用於呈現頁面的方法,然後創建了對應的視圖,並最終成功運行了應用程式。 在下一篇教程中,我們將繼續探索 Taurus.MVC WebMVC 框架的更多功能和用法。 ...
  • 一:背景 1. 講故事 很多.NET開發者在學習高級調試的時候,使用sos的命令輸出會發現這裡也看不懂那裡也看不懂,比如截圖中的這位朋友。 .NET高級調試屬於一個偏冷門的領域,國內可觀測的資料比較少,所以很多東西需要你自己去探究源代碼,然後用各種調試工具去驗證,相關源代碼如下: coreclr: ...
  • 我一直都以為c中除以2的n次方可以使用右移n位代替,然而在實際調試中發現並不都是這樣的。是在計算餘數是發現了異常 被除數:114325068 右移15計算結果:3488 除法取整計算結果:3489 右移操作計算餘數:33772 除法取整計算餘數:1005 顯然:這是不一樣的。 移位操作是一條cpu指 ...
  • 在上一篇文章中,我們介紹了ReentrantLock類的一些基本用法,今天我們重點來介紹一下ReentrantLock其它的常用方法,以便對ReentrantLock類的使用有更深入的理解。 ...
  • Excelize 是 Go 語言編寫的用於操作電子錶格辦公文檔的開源基礎庫,2024年2月26日,社區正式發佈了 2.8.1 版本,該版本包含了多項新增功能、錯誤修複和相容性提升優化。 ...
  • 雲採用框架(Cloud Adoption Framework,簡稱CAF)為企業上雲提供策略和技術的指導原則和最佳實踐,幫助企業上好雲、用好雲、管好雲,併成功實現業務目標。本雲採用框架是基於服務大量企業客戶的經驗總結,將企業雲採用分為四個階段,並詳細探討企業應在每個階段採取的業務和技術策略;同時,還 ...
  • 與TXT文本文件,PDF文件更加專業也更適合傳輸,常用於正式報告、簡歷、合同等場合。項目中如果有使用Java將TXT文本文件轉為PDF文件的需求,可以查看本文中介紹的免費實現方法。 免費Java PDF庫 本文介紹的方法需要用到Free Spire.PDF for Java,該免費庫支持多種操作、轉 ...
  • 指針和引用 當我們需要在程式中傳遞變數的地址時,可以使用指針或引用。它們都可以用來間接訪問變數,但它們之間有一些重要的區別。 指針是一個變數,它存儲另一個變數的地址。通過指針,我們可以訪問存儲在該地址中的變數。指針可以被重新分配,可以指向不同的變數,也可以為NULL。指針使用*運算符來訪問存儲在地址 ...
  • 即使再小再簡單的需求,作為研發開發完畢之後,我們可以直接上線麽?其實很多時候事故往往就是由於“不以為意”發生的。事故的發生往往也遵循“墨菲定律”,這就要求我們更要敬畏線上,再小的需求點都需要經過嚴格的測試驗證才能上線。 ...
  • 這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助 一、是什麼 許可權是對特定資源的訪問許可,所謂許可權控制,也就是確保用戶只能訪問到被分配的資源 而前端許可權歸根結底是請求的發起權,請求的發起可能有下麵兩種形式觸發 頁面載入觸發 頁面上的按鈕點擊觸發 總的來說,所有的請求發起都觸發自前端路由或 ...