提高组精英班 2017清北学堂集训笔记——图论( 三 ) _最小生成树

经典例题：繁忙的都市（Luogu 2330）
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
这题是经典的最小瓶颈生成树问题：只用边权小于等于x的边，看看能不能构成最小生成树。
在算法中，我们已经对边从小到大排过序了，所以只要用≤x的前若干条边即可。
3.最小生成树计数问题：
题目：现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。
解法：按边权排序，先选小的，相同边权的暴力求出有几种方案，将边按照权值大小排序，将权值相同的边分到一组，统计下每组分别用了多少条边。然后对于每一组进行dfs，判断是否能够用这一组中的其他边达到相同的效果。最后把每一组的方案数相乘就是答案。
换句话说：就是不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的, 排序以后先做一遍最小生成树，得出每种权值的边使用的数量x然后对于每一种权值的边搜索，得出每一种权值的边选择方案。
1 #include 2 #include 3 #define N 105 4 #define M 1005 5 #define MOD 31011 6 using namespace std; 7 struct node//定义图类型结构体8 { 9int a,b;//节点a，b 10int zhi;//a到b的权值 11 }xu[M];12 int n,m;13 int fa[N];14 int lian[N];15 int ans=1;16 int cmp(struct node x,struct node y)//从小到大排序函数 17 {18return (x.zhi
六、最短路径：
1.Floyd算法（插点法）：
通过一个图的权值矩阵求出它的每两点间的最短路径（多源最短路）。
算法描述：
一个十分暴力又经典的DP，假设i到j的路径有两种状态：
①i和j直接有路径相连：