kruskal - hzwer.com

「BZOJ3206」[Apio2013] 道路费用
DescriptionInput你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai，bi和ci，表示有一条在ai和bi之间，费用为ci的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j 前往城镇...
02015年4月27日6,675kruskal,深度搜索

「BZOJ2654」tree
Description　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。Input　　第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。Output　　一行表示所求生成树的边权和。SampleInput22101110120SampleOutput2HINT数据规模和约定0:V<=101,2,3:V<=150,..,19:V<...
42015年1月16日7,771kruskal,二分法
「BZOJ3551」[ONTAK2010] Peaks加强版
Description「题目描述」同3545Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk，表示一组询问。v=vxorlastans，x=xxorlastans，k=kxorlastans。如果lastans=-1则不变。Output同3545HINT「数据范围」同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树，但合并两结点x，y的时新建结点ext，把ext连向fa...
22014年8月30日8,899kruskal,主席树
「BZOJ2594」[Wc2006] 水管局长数据加强版
DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
52014年8月13日8,021kruskal,离线处理,link cut tree
NOI2014魔法森林
Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。...
82014年8月12日24,003kruskal,link cut tree
「BZOJ1682」Out of Hay 干草危机
DescriptionThecowshaverunoutofhay,ahorribleeventthatmustberemediedimmediately.Bessieintendstovisittheotherfarmstosurveytheirhaysituation.ThereareN(2<=N<=2,000)farms(numbered1..N);BessiestartsatFarm1.She'lltraversesomeoralloftheM(1<=M<=10,000)two-wayroadswhoselengthdoesnotexceed1,000,000,000thatconnectthefarms.Somefarmsmaybemultiplyconnectedwithdifferentlengthroads.Allfarm...
02014年7月23日4,031kruskal
「NOIP模拟赛」无线通讯网
「题目描述」国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两边都拥有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过D，这是受收发器的功率限制。收发器的功率越高，通话距离D会更远，但同时价格也会更贵。收发器需要统一购买和安装，所以...
02014年7月7日3,665kruskal
「NOIP模拟赛」征兵
一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱...
02014年7月3日3,792kruskal
「BZOJ1626」[Usaco2007 Dec] Building Roads 修建道路
DescriptionFarmerJohn最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。所有N(1<=N<=1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i,Y_i)的点(0<=X_i<=1,000,000；0<=Y_i<=1,000,000)，两个农场间道路的长度自然就是代表它们的点之间...
02014年5月23日4,143kruskal
「BZOJ2429」[HAOI2006] 聪明的猴子
Description在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示...
02014年5月18日5,250kruskal
「BZOJ1016」[JSOI2008] 最小生成树计数
Description现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。Input第一行包含两个数，n和m，其中1<=n<=100;1<=m<=1000;表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每...
52014年5月13日19,809kruskal,深度搜索
「BZOJ1977」[BJ2010组队] 次小生成树 Tree
Description小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) 这下小C蒙了，他找到了你，希望你帮他解决这个问题。Input第一行包含两个整数N和...
12014年4月28日7,198kruskal,树上倍增