【UVa】10600 ACM Contest and Blackout 次小生成树

2024-09-05 15:48

本文主要是介绍【UVa】10600 ACM Contest and Blackout 次小生成树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

类型:次小生成树


题目大意:

为了举办ACM竞赛,市长决定给所有的n(3 <= n <= 100)所学校提供可靠的电力供应。当且仅当一个学校直接连到电站,或者连到另一个有可靠供应的学校时,才有可靠供应。现在给出在不同学校之间的布线成本,找出最便宜的两种连线方案。一个方案的成本等于其中所有学校之间连线的成本的总和。


题目分析:

次小生成树。

先求出最小生成树,然后枚举所有不在树上的边(u,v),和树构成环,然后去掉形成的环中属于最小生成树上的最长边maxcost[u][v],将这条边替换进去形成新的最小生成树的权值。然后取所有新形成的最小生成树中权值最小的那一个,就是次小生成树。本题我直接用kruskal+倍增算法求解maxcost数组了,因为数据范围小,用prim时可以直接算得maxcost数组,效率不清楚。

PS:该算法同样可以判断最小生成树是否唯一。如果次小生成树的权值等于最小生成树,则不唯一,反之唯一。


代码如下:


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define LOGF( j , a , b ) for ( int j = a ; ( 1 << j ) < b ; ++ j )
#define EDGE( i , x ) for ( int i = adj[x] ; ~i ; i = edge[i].n )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )const int LOGN = 20 ;
const int MAXN = 105 ;
const int MAXE = 100005 ;
const int OO = 0x3f3f3f3f ;
struct Line {int x , y , val ;void input () {scanf ( "%d%d%d" , &x , &y , &val ) ;}bool operator < ( const Line &a ) const {return val < a.val ;}
} ;struct Edge {int v , w , n ;Edge ( int V = 0 , int W = 0 , int N  = 0 ) :v(V) , w(W) , n(N) {}
} ;struct findAndUnion {int p[MAXN] ;int rank[MAXN] ;void init () {REP ( i , MAXN )p[i] = i , rank[i] = 1 ;}int find ( int x ) {//非递归查找+路径压缩int tmp , o = x , ans ;while ( p[o] != o )o = p[o] ;ans = o ;o = x ;while ( p[o] != o ) {tmp = p[o] ;p[o] = ans ;o = tmp ;}return ans ;}//findint Union ( int x , int y ) {//合并(按秩合并)int f1 = find ( x ) ;int f2 = find ( y ) ;if ( f1 != f2 ) {if ( rank[f1] <= rank[f2] ) {//秩小的合并到秩大的点上p[f1] = f2 ;if ( rank[f1] == rank[f2] )++ rank[f2] ;}elsep[f2] = f1 ;return 1 ;}return 0 ;}//union
} ;struct MST {//并查集findAndUnion F ;int p[MAXN] ;//并查集父节点Line line[MAXE] ;//读入边集Edge edge[MAXE] ;//最小生成树边集int adj[MAXN] , cntE ;//表头及指针//倍增处理及查询(可用于LCA)int maxcost[MAXN][LOGN] ;//maxcost[i][j],最小瓶颈路int anc[MAXN][LOGN] ;//anc[i][j]表示结点i的第2^j级祖先,2^0就是父亲int cost[MAXN] ;//cost[i]表示i与父亲fa[i]之间的边权int fa[MAXN] ;//父节点int deep[MAXN] ;//结点深度int n , m ;//结点数,边数int s[MAXE] ;int top ;int ans ;void init () {top = 0 ;cntE = 0 ;clear ( adj , -1 ) ;clear ( deep , 0 ) ;}//initvoid addedge ( int u , int v , int w ) {edge[cntE] = Edge ( v , w , adj[u] ) ;adj[u] = cntE ++ ;edge[cntE] = Edge ( u , w , adj[v] ) ;adj[v] = cntE ++ ;}//addedgeint kruskal () {//求最小生成树F.init () ;sort ( line , line + m ) ;int cnt = 0 ;top = 0 ;ans = 0 ;REP ( i , m ) {int tmp = F.Union ( line[i].x , line[i].y ) ;if ( tmp ) {++ cnt ;ans += line[i].val ;addedge ( line[i].x , line[i].y , line[i].val ) ;//添加树边/*if ( cnt == n - 1 ) {//已经得到所有树边,退出return ans ;}*/}else s[top ++] = i ;//未在生成树上的边}return -1 ;//构不成树}//kruskalvoid dfs ( int u , int p ) {//得到有根树EDGE ( i , u ) {int v = edge[i].v ;if ( v == p ) continue ;fa[v] = u ;//v的父亲是udeep[v] = deep[u] + 1 ;cost[v] = edge[i].w ;dfs ( v , u ) ;}}//dfsvoid preProcess () {//预处理出anc和maxcost数组REPF ( i , 1 , n ) {anc[i][0] = fa[i] ;// i^0 级祖先就是父亲maxcost[i][0] = cost[i] ;//i与fa[i]之间的最大权值就是cost[i]LOGF ( j , 1 , n )anc[i][j] = -1 ;}LOGF ( j , 1 , n )REPF ( i , 1 , n )if ( ~anc[i][j - 1] ) {int a = anc[i][j - 1] ;anc[i][j] = anc[a][j - 1] ;maxcost[i][j] = max ( maxcost[i][j - 1] , maxcost[a][j - 1] ) ;//选择i~anc[i][j - 1]中的最大权值和anc[i][j - 1]~anc[anc[i][j - 1]][j - 1]中的最大权值//也就是i ~ (i^(j-1)) 和 (i^(j-1)) ~ i^j 中选取最大权值(子段的最大权值已经求出)}}//preProcessint query ( int p , int q ) {//查询两点间的最小瓶颈路int tmp , log = 0 , ans = -OO ;if ( deep[p] < deep[q] )//令p的深度大于等于q,不满足就交换swap ( p , q ) ;LOGF ( i , 1 , deep[p] + 1 )//得到p的最大log段( 满足 ( 1 << log ) <= deep[p] , 1 << ( log + 1 ) > deep[p] )++ log ;REPV ( i , log , 0 )//将p的深度降低到与q相同,同时求出p到q深度之间的最大权值if ( deep[p] - ( 1 << i ) >= deep[q] ) {//第2^i级祖先的深度大于等于qans = max ( ans , maxcost[p][i] ) ;p = anc[p][i] ;//跳到2^i级祖先的位置}if ( p == q )//q是p的祖先,则之前的处理直接让p下降到q的位置,p、q之间的最大权值已经求出return ans ;//LCA返回p( p 等于 q )REPV ( i , log , 0 )//比较的前提是p、q深度相同if ( ~anc[p][i] && anc[p][i] != anc[q][i] ) {//p和q深度相同,判断一个即可//同时祖先不能是同一个,保证所比较的都是唯一路径上的边,否则会跳出最近公共祖先,得到错误结果ans = max ( ans , maxcost[p][i] ) ;ans = max ( ans , maxcost[q][i] ) ;p = anc[p][i] ;//跳q = anc[q][i] ;//跳}ans = max ( ans , cost[p] ) ;ans = max ( ans , cost[q] ) ;return ans ;//LCA返回fa[p]( 它也等于fa[q] )}//query
} ;MST tree ;void work () {int u , v , k , ans = OO ;tree.init () ;scanf ( "%d%d" , &tree.n , &tree.m ) ;REP ( i , tree.m )tree.line[i].input () ;k = tree.kruskal () ;tree.dfs ( 1 , 0 ) ;tree.preProcess () ;REP ( i , tree.top )ans = min ( ans , tree.line[tree.s[i]].val - tree.query ( tree.line[tree.s[i]].x , tree.line[tree.s[i]].y ) ) ;printf ( "%d %d\n" , tree.ans , tree.ans + ans ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- )work () ;return 0 ;
}


这篇关于【UVa】10600 ACM Contest and Blackout 次小生成树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139396

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一