图的两个基本元素是点和边，与此对应，有两种方法可以构造最小生成树T。这两种算法都基于贪心算法，因为MST问题满足贪心算法的“最优性原理”，即全局最优包含局部最优。prim算法的原理是“最近的邻居一定在MST”上，kruskal算法的原理是“最短的边一定在MST上”。
第一次出现kruskal算法或prim算法
的题目，很多描述大多是紫书上的。
hdu 1233
题意：
有n个村庄需要修通道路，已知每两个村庄之间的距离，问怎么修路，使得所有村庄都连通（但不一定有直接相连的公路，只要能间接的通过公路到达即可），并且道路总成最小？请计算最小的公路总长度。
前导知识：
1.对边进行排序。可以用sort函数排序，排序后，依次把最短路的边加入到T中。
2.判断图，处理连通性问题。这个问题用并查集简单而高效，主要是判断所选的边与已经选了的边是否会构成环，如果会构成环就不选，并查集和kruskal算法是绝配。
思路：
kruskal算法+并查集。
代码：
#include<bits/stdc++.h>
using namespace std;
int fa[105];
struct Edge{
int u,v,w;
bool operator<(const Edge&a)const{
return w<a.w;
}
}edge[101*101];
int find(int u) {
return fa[u]==-1?u:(fa[u]=find(fa[u]));
}
int n,m;
int kruskal() {
int ans=0;
memset(fa,-1,sizeof fa);
sort(edge+1,edge+1+m);
for(int i=1;i<=m;++i) {
int b=find(edge[i].u);
int c=find(edge[i].v);
if(b==c) continue;
fa[c]=b;
ans+=edge[i].w;
}
return ans;
}
int main() {
while(scanf("%d",&n),n) {
m=n*(n-1)/2;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
printf("%d\n",kruskal());
}
} hdu 1102
简单题
题意：
3
0 990 692
990 0 179
692 179 0
1
1 2
一共3个村子，下面是第i行j列 i村子和j村子之间建路需要的距离
下面是一个k
代表有k条路已经修好了，1村子和2村子之间已修路。问怎么修路，使得所有村庄都连通（但不一定有直接相连的公路，只要能间接的通过公路到达即可），并且道路总成最小？请计算最小的公路总长度。
前导知识：
prim算法：对点进行贪心操作。从任意一个点u（这里假设从点u=1开始，起点dis[u]=0，更新dis[i]为i到u的距离）开始，把距离它最小的点v加入到T中；下一步，把距离{u，v}最近的点w加入到加入到T中（并更新dis[i]为到u或v的最短距离）；继续这个过程，直到所有的点都在T中。
思路：
prim算法。
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n,q,a,b;
int dis[maxn], vis[maxn], e[maxn][maxn];
int Prim() {
int ans=0;
for(int i=0; i<=n; ++i) dis[i]=100000, vis[i]=0; //初始化
dis[1]=0; //prim算法任选起点，于是可以选择1为起点
for(int i=1; i<=n; ++i) {
int u=0; //注意dis[0]已经初始化为无穷大了，不用管了
for(int j=1; j<=n; ++j) if(!vis[j]) {
if(dis[j]<dis[u]) u=j;
}
vis[u]=1; ans+=dis[u]; //更新答案啦
for(int j=1; j<=n; ++j) if(!vis[j]) { //拿u点来更新新拓展的边
if(dis[j]>e[u][j]) dis[j]=e[u][j];
}
}
return ans;
}
void solve() {
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j) scanf("%d", &e[i][j]);
scanf("%d",&q);
for(int i=0;i<q;++i) {
scanf("%d%d",&a,&b);
e[a][b]=e[b][a]=0;
}
printf("%d\n", Prim());
}
int main() {
while(~scanf("%d", &n)) {
solve();
}
} hdu 3938
离线算法+kruskal算法+并查集
题意：给你n个顶点，m条边，以及q次询问。
之后给出m条边的起末点及边权值，在q次询问，每次给你一个价值wal,问 这个价值你能在这个图里走多少种路。每一条路的权值是这条路中最大边的权值。
思路：用结构体存每次询问的价值和序号，按价值从小到大排序，因为小价值能走的路大价值也一定能走。每次加入一条边会连通两个集合，路径数就等于两个集合中元数的乘积，并查集可以做到存该集合的元数个数，kruskal算法选边是从小到大，所以放入的当前边一定是两个集合构成的所有路径的权值（该路径的起点、终点分别在不同的集合，如果在一个集合就会和前面的计算重了）。把目前算出的方案总数赋值给价值最小的询问，直到询问的最小价值小于当前的边，才把方案数赋值给价值大一点的（注意：因为可能询问价值大一点点也的还是小于当前的边，所以要把现在询问价值的路径数赋值给大一点的询问价值，如果大一点点的价值大于当前的边，就用现在路径总数跟新它），一直执行这个操作，直到边都选完了，如果还有询问的价值没有答案，说明价值偏大了，把现在的路径总数赋值给没有答案的询问，最后按顺序输出。
Code：
#include<bits/stdc++.h>
using namespace std;
int size[100005],fa[100005],sum[100005];
struct node{
int id,val;
bool operator<(node a) const{
return val<a.val;
}
}q[100005];
struct edge{
int u,v,val;
bool operator<(edge a) const{
return val<a.val;
}
}f[100005];
int find(int x) {
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int n,m,Q,ans,t;
void solve() {
for(int i=1;i<=m;++i) {
int x=find(f[i].u),y=find(f[i].v);
if(x!=y) {
ans+=size[x]*size[y];
fa[x]=y;
size[y]+=size[x];
while(q[t].val<f[i].val) {
++t; sum[q[t].id]=sum[q[t-1].id];
//cout<<q[t].id<<"不配"<<sum[q[t].id]<<endl;
}
sum[q[t].id]=ans;
//cout<<q[t].id<<" "<<sum[q[t].id]<<endl;
}
}
while(t<Q) sum[q[++t].id]=ans;
}
int main() {
while(scanf("%d%d%d",&n,&m,&Q)==3) {
for(int i=1;i<=n;++i) {
fa[i]=i;
size[i]=1;
}
for(int i=1;i<=m;++i)
scanf("%d%d%d",&f[i].u,&f[i].v,&f[i].val);
sort(f+1,f+1+m);
for(int i=1;i<=Q;++i) {
scanf("%d",&q[i].val);
q[i].id=i;
}
sort(q+1,q+1+Q);
ans=0,t=1;
solve();
for(int i=1;i<=Q;++i) printf("%d\n",sum[i]);
}
} poj 2377
最小生成树的扩展，最大生成树。
题意：n个点m条边，接下来m行表示连接i和j的花费val，将所有的点连接，要保证不能成环，花费最大，所有的点都在一个连通块里。如果所有的点不在一个连通块就输出-1，否则输出最大花费。
思路：因为要判断是否所有的点都在一个连通块，所以用kruskal算法+并查集最好，把边按从大到小排序。记录合并了多少条边，如果所有的点在一个连通块，连接的边应该有n-1个。
Code：
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,ans=0,cnt=0,f[1005];
struct Node{
int x,y,w;
bool operator<(Node a) const{
return w>a.w;
}
}node[20005];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w);
sort(node+1,node+1+m);
for(int i=1;i<=m;i++){
int fx=find(node[i].x),fy=find(node[i].y);
if(fx!=fy)f[fx]=fy,cnt++,ans+=node[i].w;
}
if(cnt==n-1)printf("%d\n",ans);
else puts("-1");
} hdu 5627
注意：和poj2377一样的思路，题目也差不多，就是如果全部的点不在一个连通块里就输出-1，而且最大生成树的值是每个边异或的值，不是每个边的和。这两个题目不建议都写，浪费时间。
Code：
#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,cnt,f[300005];
struct node{
int x,y,w;
bool operator<(node a) const{
return w>a.w;
}
}q[300005];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].w);
sort(q+1,q+1+m);
ans=cnt=0;
for(int i=1;i<=m;i++){
int fx=find(q[i].x),fy=find(q[i].y);
if(fx!=fy)f[fx]=fy,cnt++,ans^=q[i].w;
}
if(cnt==n-1)printf("%d\n",ans);
else puts("0");
}
} hdu 4081
次小生成树
题意：给n个位置的坐标以及每个坐标的人数，让所有的城市联通，并且我们还有一次施放魔法的机会（连接任意两个城市），让我们求A/B的最大值，A表示两个城市的人数 B表示剩余城市全部联通所需修建的路长。
思路：我们会发现如果我们要去掉的边g[i][j]在最小生成树上，那么我们直接用最小生成树的值减去我们要去掉的边的g[i][j]，如果不在，那么直接用最小生成树的值减去path[i][j]（表示加上g[i][j]这条边后要生成次小生成树要去的边的权值--次小是相对与这个限制条件而言，即加上边g[i][j]和保证树的值最小）。
那么path[][]怎么求：假设这时最小生成树新加的点是u，u和pre[u]是一条边上的端点，j已经在最小生成树里面了，那么可得path[j][u]=path[u][j]=max(path[j][pre[u]],dis[u])。
为什么u和j连线要去的边一定和u的另一个端点pre[u]（dis[u]就是u和pre[u]的边）有关呢。
比如求path[1][4]，u=4，j=1，如果连接1-4，会形成一个环，而path[1][4]的值就是环中除了加入的边中权值最大的边，可以看成是pre[4]=2和1成环后要去的边（因为1-2是最小生成树上的，所有path[1][2]=0）或者u和pre[u]的边，两者之间取最大值。为什么不是max(path[1][5],dis[4])呢，显然会出现不连通的情况。
上面我解释不清，下面再扯一点。
最小生成树生成后，假设加入我们要连1-4(1假设设是不等于u和pre[u]的任意点，2假设是pre[u]，4假设是u)，那么将就会生成一个环，我们先把某条权值最大的边去掉，1和2会被分成两个连通块或者只要去掉2-4（也就是u-pre[u]）就可以。如果1和2被分成两个连通块，由于1-4和2-4的存在，所有的点又将联通，如果是去掉2-4，由于1-4的存在，所有的点又将联通。所有只有这样的表达式才能保证在求得的path[j][u]尽可能大的情况下所有的点是连通的。
code：
#include<bits/stdc++.h>
#define scanf1(a) scanf("%d",&a)
#define scanf2(a,b) scanf("%d%d",&a,&b)
#define mes(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f
using namespace std;
double g[1005][1005],path[1005][1005],pos[1005][2],dis[1005],cost[1005],mincost,ans;
int fa[1005],val[1005],pre[1005],used[1005][1005];
int t,n;
int find(int x) {
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void prime() {
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) path[i][j]=used[i][j]=0;
for(int i=1;i<=n;++i) {
fa[i]=i;
val[i]=0;
dis[i]=g[1][i];
pre[i]=1;
}
val[1]=1;
for(int i=1;i<n;++i) {
int u=0;
for(int j=1;j<=n;++j) if(!val[j]){
if(dis[j]<dis[u]) u=j;
}
used[u][pre[u]]=used[pre[u]][u]=1;
mincost+=g[pre[u]][u];
val[u]=1;
for(int j=1;j<=n;++j) {
if(!val[j]) {
if(dis[j]>g[u][j]) {
dis[j]=g[u][j];
pre[j]=u;
}
}
else if(j!=u)
path[j][u]=path[u][j]=max(path[j][pre[u]],dis[u]);
}
}
}
inline double get(double x,double y, double a,double b) {
return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int main() {
scanf1(t);
dis[0]=inf;
while(t--) {
scanf1(n);
for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&pos[i][0],&pos[i][1],&cost[i]);
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j) g[j][i]=g[i][j]=get(pos[i][0],pos[i][1],pos[j][0],pos[j][1]);
mincost=ans=0.0;
prime();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) if(i!=j)
if(used[i][j])
ans=max(ans,(cost[i]+cost[j])/(mincost-g[i][j]));
else
ans=max(ans,(cost[i]+cost[j])/(mincost-path[i][j]));
printf("%.2f\n",ans);
}
} hdu 4126
题意：（次小生成树）
给出一个连通的无向图，每一条边都有权值，现在有q次询问，每次都会更改一条边的cost，问q次询问更改之后的平均最小生成树是多少。（n个城市，m条路，编号0 ~ n-1）
.注意更改的变的cost比原来大。
.所有询问互不干扰
思路：考虑到一条边改变有两种情况
1.改的边不是生成树上的边，对生成树的权值没有影响，最近加上mincost。
2.改的边是原来生成树上的边，把这条边去掉就会形成两棵树，只要找到这两颗树的最小距离就是生成树新边的权值。
树形dp求出非生成树的边最短距离连接两颗断掉的最小生成树，dp[u][v]表示生成树上的边u-v断掉后从u的子树到v子树的最短距离，也就意味着找一条新边替换原来的边。
dfs求dp[u][pre[u]]的原理：（以上图为例，画图后真的好理解多了）
1.dfs(5,5,-1)最后一层求得cost=g[5][3]=9，返回上一层时dp[3][4]=min(dp[3][4],上一层的cost)=9，cost=min(上一层返回值cost，g[5][4])=9，继续同一层求得cost=g[5][1]=6，返回到上一层时dp[2][4]=9，dp[2][1]=6（过程不累赘了），cost=min(6,9)=6。最后回到第一层得dp[5][2]=6。注意：为什么dp[3][4]不可以等于遍历过程中边的始端到4到5的距离，而一定要是终端3到5的距离呢？结合dp[u][v]的意义，因为5和4在同一个子树，如果dp[3][4]可以取g[4][5]，那么就会成环。
其实就是这样一个过程，从一个点r出发,r的另一个端点是s，现在点的位置是u，边的另一端是v，求得（此时s!=v）g[r][v]中的最小值，最后将最小值复制给dp[5][2]，也就是说一个作用是求结点5到结点2所在子树的最短距离（非生成树上的最小边）。但是这样还不够，dp[u][v]是u子树到v子树的最短距离（非生成树上的最小边），从一个点r出发,r的另一个端点是s，现在点的位置是u(u前面的一个点是k)，边的另一端是v，求得（此时s!=v）g[r][v]或min(g[r][v],g[r][u])，接着dp[u][v]=min(dp[u][v],g[r][v])或者dp[k][u]=min(min(g[r][v],g[r][u]),dp[k][u])，比如dp[3][4]=9，dp[2][4]=min(9,10)=9，也就是说另一个作用就是可以取到u（比如4）子树上的结点r（比如5）到v（比如3）的距离。
我都不知道自己在说什么了，看不懂不要太纠结，参考就行，多画图，这个图就不错（不是说画画画得好，是这个模型好，没讨论的边没画）。
for(int i=0;i<n;++i) dfs(i,i,-1);递归出口就是取到i结点到边的另一端的子树的最短距离，子递归就是求边的始端子树中的结点i到总端子树的最短距离。所以dfs每一个点就可以取到u子树到v子树的最短距离（非生成树上的最小边）。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,q,e,mincost;
int dis[3000],val[3000],g[3000][3000],dp[3000][3000];
int pre[3000],Next[6000],head[3000],node[6000];
void addedge(int u,int v) {
node[e]=v; //属于顶点u的e边的另一个端点是v
Next[e]=head[u]; //Next[e]数组记录顶点u在边e之前的一个边；
head[u]=e++; //head[u]更新下一个顶点u的Next[e]数组的取值
//head[u]的最终取值还是u中最先遍历的边
}
void prim() {
for(int i=1;i<n;++i) if(dis[i]>g[0][i]) {
dis[i]=g[0][i];
pre[i]=0;
}
val[0]=1; e=mincost=0;
for(int i=0;i<n-1;++i) {
int u=-1;
for(int j=1;j<n;++j) if(!val[j]&&(u==-1||dis[u]>dis[j])) u=j;
mincost+=dis[u];
val[u]=1;
if(pre[u]!=-1) {
addedge(u,pre[u]);
addedge(pre[u],u);
}
for(int j=1;j<n;++j) if(!val[j]&&(dis[j]>g[u][j])) {
dis[j]=g[u][j];
pre[j]=u;
}
}
}
int dfs(int r,int v,int u) {
int cost=inf;
for(int i=head[v];i!=-1;i=Next[i]) if(node[i]!=u) {
int temp=dfs(r,node[i],v);
cost=min(cost,temp);
dp[v][node[i]]=dp[node[i]][v]=min(temp,dp[node[i]][v]);
}
if(r!=u) cost=min(cost,g[r][v]);
return cost;
}
int u,v,w;
int main() {
while(scanf("%d%d",&n,&m)&&n+m) {
for(int i=0;i<n;++i) {
for(int j=0;j<i;++j)
g[i][j]=g[j][i]=dp[i][j]=dp[j][i]=inf;
pre[i]=-1;
val[i]=0;
dis[i]=inf;
}
memset(head,-1,sizeof(head));
for(int i=0;i<m;++i) {
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=w;
}
prim();
for(int i=0;i<n;++i)
dfs(i,i,-1);
scanf("%d",&q);
double ans=0.0;
for(int i=0;i<q;++i) {
scanf("%d%d%d",&u,&v,&w);
if(pre[u]==v||pre[v]==u)
ans+=mincost-g[u][v]+min(w,dp[u][v]);
else
ans+=mincost;
}
printf("%.4f\n",ans/q);
}
} 
京公网安备 11010502036488号