撰写- 两个性质
- 切割性质
- 假定所有边权均不相同。
- 设S为既非空集也非全集的V的子集，边e是满足一个端点在S内，另一个端点不在S内的所有边中权值最小的一个，则图G的所有生成树均包含e
- 回路性质
- 假定所有边权值均不相同。设C是图G中的任意回路，边e是C上权值最大的边，则图G的所有生成树均不包含e
- 切割性质
- 增量最小生成树
- 从包含n个点的空图开始，依次加入m条带权边。每加入一条边，输出当前图中的最小生成树权值（如果当前图不连通，输出无解）
- 解答：
- 如果每次重新求解完整的最小生成树问题，总时间复杂度高达O(m^2logn)
- 实际上，根据回路性质，我们可以得到如下的改进算法：每次求出新的最小生成树后，把其他所有边删除，由于每次只需要计算一个n条边（原有生成树有n-1条，新加入一条）的图的最小生成树，Kruskal算法的时间复杂度降为O(nlogn)，总时间为O（nmlogn）
- 这个算法还可以进一步改为，加入一条边e=(u,v)后，图中恰好包含一个环，加入一条边e=(u,v)之后，图中恰好包含一个环，根据回路性质，删除该回路上权值最大的边即可，因此只需要加边之前的MST上找到u到v的唯一路径上权值最大的边，再和e比较，删除权值较大的一条，由于路径唯一，可以用dfs或者bfs找到这条u到v的路径，总时间复杂度为O(nm)
-
struct Node { int u,v; int val; bool operator<(const Node& rhs)const { return val<rhs.val; } } edge[N]; int n,m,cnt; int father[N]; int Find(int x) { if(father[x]==x) return x; return father[x]=Find(father[x]); } void Kruskal() { sort(edge,edge+cnt); int pos=-1; int res=0,mst=0; for(int i=0; i<cnt; i++) { int u=edge[i].u,v=edge[i].v; int x=Find(u),y=Find(v); if(x!=y) { father[x]=y; res++; mst+=edge[i].val; } else { pos=i; continue; } } if(pos!=-1) edge[pos]=edge[--cnt]; if(res!=n-1) printf("-1\n"); else printf("%d\n",mst); } int main() { scanf("%d%d",&n,&m); cnt=0; for(int i=0; i<m; i++) {//添m次边 scanf("%d%d%d",&edge[cnt].u,&edge[cnt].v,&edge[cnt].val); cnt++; for(int i=0; i<N; i++) father[i]=i; Kruskal();//每次添边跑一次Kruskal } return 0; }
- 最小瓶颈生成树
- 由于只关心最大边权值，我们可以从一个空图开始，按照权值从小到大得顺序依次加入各条边，则图第一次连通时，该图得的最小生成树就是原图的最小瓶颈生成树。实际上，就是Kruskal……所以原图的最小生成树就是一棵最小瓶颈生成树
- 最小瓶颈路
-
- 给定加权无向图的两个结点u和v，求出从u到v的一条路径，使得路径上的最长边尽量短
- 这个问题可以用二分+bfs解决
- 最小化最大值，考虑采用二分搜索。对所有的边长进行排序，二分，对每次选择的边长，判断是3否存在一条路径满足路径上所有的边长度均小于等于该边长，使用BFS搜索，因为BFS用于寻找最短（边的个数最少）路径。
- 但是我们有更好的算法
- 先求出这个图中的最小生成树，则起点和终点在树上的唯一路径就是我们要找的路径，这条路径上的最长边就是问题的答案
-
int prim(int s) { int res=0; memset(maxcost,0,sizeof(maxcost)); for(int i=1;i<=n;i++) vis[i] = 0, d[i] = INF, pre[i]=i; d[s]=0; for(int i=0;i<n;i++) { int maxx=INF, index=-1; for(int j=1;j<=n;j++) { if(!vis[j]&&d[j]<maxx) { maxx=d[index=j]; } } if(index==-1) break; for(int j=1;j<=n;j++) if(vis[j]) maxcost[index][j] = maxcost[j][index] = max(maxcost[pre[index]][j], maxx); res+=maxx; vis[index]=1; for(int j=1;j<=n;j++) { if(!vis[j]&&g[index][j]<d[j]) { d[j] = g[index][j]; pre[j] = index; } } } return res; } -
struct Edge{ int u,v,w; Edge(int u=0,int v=0,int dist=0):u(u),v(v),w(dist){} }e[maxm]; vector<Edge> vec[maxn]; bool cmp(const Edge& a,const Edge& b){ return a.w<b.w; } int find(int x){ return p[x]==x?x:p[x]=find(p[x]); } void kruskal() { sort(e,e+m,cmp); for(int i=1;i<=n;i++) p[i]=i; int cnt=0; for(int i=0;i<m;i++){ int x=find(e[i].u),y=find(e[i].v); if(x!=y){ p[y]=x; vec[e[i].u].push_back(Edge(e[i].u, e[i].v, e[i].w)); vec[e[i].v].push_back(Edge(e[i].v, e[i].u, e[i].w)); if(++cnt==n-1) break; } } } void dfs(int index) { vis[index]=1; for(int i=0;i<vec[index].size();i++) { int tmp=vec[index][i].v; if(!vis[tmp]) { for(int j=1;j<=n;j++) if(vis[j]) { maxcost[j][tmp] = maxcost[tmp][j] = max(maxcost[j][index], vec[index][i].w); } pre[tmp]=index; dfs(tmp); } } }
-
- 每对结点间的最小瓶颈路
- 给出加权无向图，求每两个结点u和v之间的最小瓶颈路的最大边长f(u,v)
- 不难想到先求出最小生成树，然后用dfs把最小生成树变成有根树，同时计算f(u,v)，当新访问一个结点u时，考虑所有已经访问过的老结点x，更新f(x,u) = max(f(x,v), w(u,v))，其中v是u的父结点。每个f(u,v)只需常数时间计算，因此时间复杂度为O(n^2)
- 次小生成树
- 把所有生成树按照权值之和从大到小的顺序排列，求排在第二位的生成树。
- 可以枚举最小生成树中不在次小生成树中出现的边，因为最小生成树只有n-1条边，所以只需要枚举n-1次，每次在剩下的边里求一次最小生成树，则这n-1棵“缺一条边的图”的最小生成树中权最小的就是原图的最小生成树，时间复杂度为O(mna(n,m)) 注意边只要排序一次
- 实际上，我们只需要枚举要加入哪条边，在最小生成树上加一条边u-v之后，图上会出现一条回路，因此删除的边必须在最小生成树u到v的路径上，而且是这条路径上的最长边，可以证明，次小生成树一定可以由最小生成树加一条边再删一条边得到，因此只需要按照“每对结点之间”的“最小瓶颈路”的方法求出每对结点u和v在最小生成树中唯一路径的最大边权maxcost[u][v]，则剩下部分只需要O(m)时间（枚举所有m-n+1条边）进行交换，每次花费O(1)时间求出新生成树的权值，总复杂度为O(n^2)
-
const int maxn = 1e6+10; const int INF=0x3f3f3f3f; double cost[1010][1010],lowc[2010],ans; int n,m; bool vis[3010]; double Max[1010][1010]; int pre[2020]; bool used[1010][1010]; double prim(){ double ans = 0; memset(vis,false,sizeof(vis)); memset(Max,0,sizeof(Max)); memset(used,0,sizeof(used)); vis[0]=true; pre[0]=-1; for(int i=1;i<n;i++){ lowc[i]=cost[0][i]; pre[i]=0; } lowc[0]=0.0; for(int i=1;i<n;i++){ double minc = INF; int p=-1; for(int j=0;j<n;j++){ if(!vis[j]&&minc>lowc[j]){ minc=lowc[j]; p=j; } } if(minc==INF)return -1; ans += minc; vis[p]=true; used[p][pre[p]]=used[pre[p]][p]=true; for(int j=0;j<n;j++){ if(vis[j] && j!=p)Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]); if(!vis[j] && lowc[j]>cost[p][j]){ lowc[j] = cost[p][j]; pre[j]=p; } } } cout<<ans<<endl; //这里的ans是最小生成树的，需要枚举不在used数组里的边进行替换得出答案 return ans; }
- 最小有向生成树
