今天我們先來講一下狀態壓縮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都有的。差分約束因為本蒟蒻太蒟蒻了，所以明天問問老師再寫吧！！最後說一下，明天我們要考試了，因為對於作者一個六升七的孩紙來說老師說是信奧提高組及以上的知識，所以我們幾個六升七的已經約定好一起爆零了，明天已經放平心態了。。。。。。
--------------------------------------------------------------------------------------分割線-----------------------------------------------------------------------------------------
開玩笑噠！！明天一定要加油加油加油！！！
