今天我们先来讲一下状态压缩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都有的。差分约束因为本蒟蒻太蒟蒻了，所以明天问问老师再写吧！！最后说一下，明天我们要考试了，因为对于作者一个六升七的孩纸来说老师说是信奥提高组及以上的知识，所以我们几个六升七的已经约定好一起爆零了，明天已经放平心态了。。。。。。
————————————————————————————–分割线—————————————————————————————–
开玩笑哒！！明天一定要加油加油加油！！！
声明：本站所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
