次小生成树学习+例题 poj 1679 The Unique MST
次小生成树学习:
顾名思义,次小生成树,就是将图的所有生成树排序后,权值第二小的生成树。
次小生成树的朴素求法是很好想的,即首先求出最小生成树,之后枚举最小生成树中的所有边,将当前枚举的边“禁止使用”,在这基础之上再求最小生成树,将所有边枚举之后的结果取最小值,那就是次小生成树。这个算法简单暴力,但是可想而知的复杂度是比较大的,在图是稠密图的时候,复杂度接近O(n^3)。在规模较大的时候不建议使用。
另一个推荐的求法:在添加最小生成树的边之外的边时,会形成环,这个时候,把在这个环中,且在最小生成树中的边给去掉,这时候就形成了另一个生成树。如何实现这个算法的呢?实际上,对于两个点u,v,我们遍历最小生成树,找出u到v的边中的最大权值的边,用一个数组maxn[u][v]保存起来。当我们往最小生成树中加边时,就直接用w - max[u][v] + 当前添加边的权值,这个式子计算出此时生成树的权值之和。那么maxn[u][v]这个数组是如何求得呢?嗯,bfs,即广度优先搜索,对每一个点都遍历一次生成树,每次更新的值都是当前点到其他点的权值。之后就枚举不在生成树的边进行计算,把每次的结果都保存下来,取最小的,就是次小生成树啦。(或许第k小生成树可以这么求?)这个算法的复杂度为O(n^2)。
例题:
https://vjudge.net/problem/POJ-1679
题意:
这题问的是最小生成树是否唯一。
思路:
那么很显然的,如果说最小生成树不唯一的话,那么最小生成树与次小生成树的权值肯定相等,因为对于在最小生成树中的边来说,至少存在一条不在其中的边,与在其中的边的权值相等,这样才满足不唯一,所以只需要求出次小生成树,判断其与最小生成树是否相等就可以了。
PS:通过这题还学会了用邻接链表表示图,用vector很方便的,就是把以每个点为起点的边搞到一起就ok。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std; struct node
{
int x,y,w;
} e[]; struct ord
{
int p,dis;
}; vector<node> v[]; int par[];
int maxn[][]; bool used[],vis[]; void init(int n)
{
for (int i = ;i <= n;i++)
par[i] = i;
} int fin(int x)
{
if (x == par[x]) return x;
else return par[x] = fin(par[x]);
} void unit(int x,int y)
{
x = fin(x);
y = fin(y); if (x != y) par[x] = y;
} bool cmp(node aa,node bb)
{
return aa.w < bb.w;
} void adde(int x,int y,int dis)
{
node t;
t.x = x;
t.y = y;
t.w = dis;
v[x].push_back(t);
} void bfs(int k)
{
memset(used,,sizeof(used)); ord now,nex; now.p = k;now.dis = ;
used[k] = true; queue<ord> qq; while (!qq.empty()) qq.pop(); qq.push(now); while (!qq.empty())
{
//printf("dsfsd\n");
ord t = qq.front();qq.pop(); int x = t.p,tmaxn = t.dis; for (int i = ;i < v[x].size();i++)
{
node tt = v[x][i]; nex.dis = tt.w;nex.p = tt.y; if (!used[nex.p])
{
if (tmaxn > nex.dis) nex.dis = tmaxn;
used[nex.p] = true;
maxn[k][nex.p] = nex.dis;
qq.push(nex);
}
}
}
} int main()
{
int t; scanf("%d",&t); while (t--)
{
int n,m; scanf("%d%d",&n,&m); init(n); memset(v,,sizeof(v));
memset(vis,,sizeof(vis));
memset(used,,sizeof(used)); for (int i = ;i < m;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
} sort(e,e+m,cmp); int ans = ; for (int i = ;i < m;i++)
{
int x = e[i].x,y = e[i].y; if (fin(x) == fin(y)) continue; unit(x,y); vis[i] = true; ans += e[i].w; adde(x,y,e[i].w);
adde(y,x,e[i].w);
} for (int i = ;i <= n;i++)
{
bfs(i);
} int minn = ; for (int i = ;i < m;i++)
{
if (!vis[i])
{
int tans = ans;
int x = e[i].x,y = e[i].y; tans -= maxn[x][y]; tans += e[i].w; if (tans < minn) minn = tans;
} } if (minn == ans) printf("Not Unique!\n");
else printf("%d\n",ans);
} return ;
}
最新文章
- wx getlocation
- next()与nextLine的区别
- asp.net 验证正则表达式
- Ecological Premium
- 业务gis 搭建一个skyline 的js模板 (一)
- Http相应代码及获取方法
- PHP导出数据库数据字典脚本
- dedecms网站文章标题与简标题的调用问题
- 批处理安装nodejs
- 【JAVAWEB学习笔记】21_多条件查询、attr和prop的区别和分页的实现
- 建立maven工程pom.xml报错:web.xml is missing and <;failOnMissingWebXml>; is set to true
- ThinkPHP中ajax绑定select下拉框无法显示
- Java Random介绍
- npm run dev 出错的解决办法
- 闪回工具flashback
- 通用查询设计思想(2)- 基于ADO.Net的设计
- react axios 配置
- kindedit编辑器和xxs攻击防护(BeautifulSoup)的简单使用
- 长度不超过n的连续最大和___优先队列
- Linq的执行效率及优化