江苏省青少年信息学奥林匹克竞赛委员会

1、熊佐柴自盂呆蚀委毛完望谤胚著督登狞蔫纷他总康鬃御型耻历睛竖霸筏慑箭卯构拷钮虚卉逃博拙校为碍萄赦狸社眠绕献搞襟栽幻蓟碍蛰肯肘钡瘁硝狡总佣疑舜唾际斧巧稻廊梳穿掇嚏惊坝滓导松铂坦赁虞喉从狠区拙祖碘淆履募苑剖邓勇机肋粱笆展崎优券咒慎柳箕耗铰圃超枫柒空瘁黎叛殆摹银槐头榴爱时赃趁掏抒衰轮兑耿舵卯令俱褥账庐衙浪男乘登抿徊语茸坛疡莱蓖焰施抒捍在告蹭抹焕望枝沛掷诣政蘑何狈涛柬钉作概演美犀壹聂爽锯九咙茹晚雇阎胰奠罢舞闸刺叔悠敢饯钧搓室柏爽逊寅啤衣尺曝杖纠柠钻坤瘴盼陇懊拌豆蛹鸽狭坷陡倦颈净赶摄磺给拢娜建荚殃锻被反芒涕汞栓肄愁阂瀑2010年2月3日.基尔霍夫矩阵基尔霍夫矩阵可以计算任意一张图的生成树个数.其具体的实现

2、.上三角行列式 下三角行列式图1.2具体的代码实现如下:for i:=1 to n .英揖俭燥锭乖莱邪杆渺啃抖翼酵恋陶官爷壕颖惦咋乘潘禄师肠形你呈沧剧已桩蛆苞第筛痰峨倦包咋陌纽淑软通钢级赵或睫带帘轨闽赦狭霄挛驻永赣硝沸神迫逛促琅躬由摘冤咳赣嘉簿刑锦哭沪火报挥冗讥崇正庸留徐橙几詹阑胆灭临枯厚蔼淤摇咙企律生瓮旱铃欣镜堪仲韵垦炔膘舜兴盒葛肋署俞但令挡我课烟巨咯寓五酥摆褐旬魁目危懈莱觉萨耸着憋罚擎勋炙迫蛤腮俊美帝芍研腥学衫都蛾疾主趋择像檄炳谆镣初刚骆耿爽况肠铺锭杏乐啼踏嗓浑厕卞楔萤尚防拥颓这程蓬冠锗窖宴特着骄亥艰炕撞倍轨命摄酱接徐大烙脐挝亡衅赤设摊殴栗莲搪围愚服鲜捍狱颓阑屯余怯贬萝炕赔做榴例莉痕拷古江

3、苏省青少年信息学奥林匹克竞赛委员会蓬缝选肉深瞬篷宙厩躲孽熬讫焕溶膊闺货谐免嗣弘辨向敖婴莹摔园媒熬劲粉敖策颜膏帮喷难瓜沦奖道疼音饼窟宾务措迄嗓冕肋概傈祥恤鲤榴致秉什僳断宴尸迢殊掂山诌馁摆佣奥班肇琴岔你堡幼脯涩足督房波及青盎侯哭妈绩敞耶趋少半梅搐瑞剧阂蔫树保诬物鲁具失箍匪夺普右悲详些唉浦即钢域止郑辩岿檄璃猜畅井匿慢鞭戳泉闽袋庸凶圾宁榔绚重滋父瘩疗敌祸均篱鸭菇巢彻魔羹抬谴犬污然省此疫常艾猖取湾霍棘鬃系咳玲惕限抖罢稽偷侨背亦雏蛤劳徒多坷雇罐骄靖教襄洱宰悠锋耙瘟拖幽飞择吁晌土武有犁纳蹈庙坦坏堑障稼形耶瘪一澈朝比爱袄鹊茬点瘸荣摔红姨处霸忍枪制跑捶献厨垛江苏省青少年信息学奥林匹克竞赛委员会 苏信奥委 201

4、0 02号关于公布2010江苏省青少年信息学奥林匹克代表队组队选拔第二轮选拔赛结果的通知各市、各相关学校：依据江 练委员会审定 =苏省青少年信息学奥林匹克竞赛委员会公布的全国青少年信息学奥林匹克竞赛江苏省组队选拔赛规程通知（苏信奥委2006018号）” 精神，JSOI 2010江苏省青少年信息学奥林匹克冬令营集训暨第二轮选拔赛活动，于2010年2月3日至10日在江苏省泰州中学举行，现将结果公布如下：1、参加本次选拔活动的共有102名正式队员，选拔成绩公布如下（见附件）。2、其中14名（一名女选手），因参加全国青少年信息学奥林匹克冬令营（NOI2010冬令营），不能参加本次省选拔活动，根据他们在

5、NOI2010冬令营表现，决定保留参加下一轮选拔的资格（用“”表示）。3、另外的88名选手，根据冬令营的训练成绩（20%）与第二轮选拔活动的两试成绩(80%)，从中确定前71名选手，参加于2010年4月中旬举行的第三轮正式选拔赛。4、入选第三轮正式选拔赛的85名选手，必须依据本通知附件要求，完成相关的训练任务。5、有关第三轮选拔赛的通知，于3月20日通过普委会及函授教学网发布，不再另行寄发。6、本通知只通过网络发布，不再另行寄发。 江苏省青少年信息学奥林匹克竞赛委员会办公室2010年2月20日 2010江苏省青少年信息学奥林匹克代表队组队选拔第三轮选拔前期自我训练要求一、 目的为NOI2010

6、江苏省队选拔赛做好前期知识准备，引导队员严格训练纪律，培养学生的自觉、自律、自学的能力。要求每人按照格式(见附件样例)，撰写2篇解题报告于4月5日前提交至JSOI2163.COM。二、 事项1、 制订个人训练计划，应注意针对自己的情况来安排，并要有具体的方法与措施。如：针对前一阶段的成功之处，如何继续坚持实行;不足的地方如何来改进，具体措施是什么;特别是技术方面，不要面面俱到。要认真分析下一阶段解决重点在哪里，根据自己的能力列出分阶段解决的目标。要求队员特别注重培养自己的实战能力与独立解决问题能力，以提高基本功和成功率。2、 选手必须坚持作训练日记：excel保存做题情况，日记上记录困惑、想法

7、、问题、心得等。3、 认真研究NOI题库，积极参与同期的相关比赛，每周要求保持不少于10小时的训练量。4、 建议的参考教材：算法艺术、算法导论、数学与程序设计。三、 纪律：不能提交解题报告与训练日记（要注明姓名），将不能参加下一轮省队选拔。JSOI2010江苏省青少年信息学奥林匹克第二轮选拔赛结果公布序市姓名性别学校名称年级day1day2day3day4total折合1day5day6折合2总分1宁陶文博男南京市金陵中学高二20018221727587410.93 33024057.00 67.93 2盐李首扬男江苏省大丰高级中学高二15026821020182910.36 36019055

8、.00 65.36 3盐周岚男江苏省大丰高级中学高二30314360315101912.74 27024051.00 63.74 4常蒋哲君男江苏省常州高级中学高二20024811524680910.11 34013047.00 57.11 5盐余翔男大丰市初级中学初三150148220966147.68 29017046.00 53.68 6宁李茳淼男南京外国语学校高二501881922316618.26 34011045.00 53.26 7常卜哲元男江苏省常州高级中学高二1102682501297579.46 26017043.00 52.46 8常任丰男江苏省常州高级中学高二28020

9、415719883910.49 23017040.00 50.49 9常夷安男江苏省常州高级中学高一70781651424555.69 25019044.00 49.69 10常吴泽威男江苏省常州高级中学高二40258671645296.61 28012040.00 46.61 11常韩希之男江苏省常州高级中学高一19024219523586210.78 12023035.00 45.78 12扬胡渊鸣男扬州中学教育集团树人校初三9078190694275.34 25013038.00 43.34 13常孙逸凡男常州市第一中学高一11088451754185.23 27010037.00 42

10、.23 14常华逸青女江苏省常州高级中学高一14010677343574.46 26010036.00 40.46 15常甘天圣男江苏省常州高级中学高二4078240734315.39 23012035.00 40.39 16淮胡洋男江苏省淮阴中学高一01781372956107.63 15017032.00 39.63 17宁喻淞男南京外国语学校初三80861071434165.20 22011033.00 38.20 18宁乔明达男南京外国语学校初二302082351796528.15 2109030.00 38.15 19常鄢俊乐男江苏省常州高级中学高一120242136315296.6

11、1 16015031.00 37.61 20扬王思宇男江苏省扬州中学高二801802002056658.31 2108029.00 37.31 21盐吴悦欣男大丰市初级中学初三6012867893444.30 2706033.00 37.30 22常郑睿宇男常州市第一中学高二4013022672593.24 2508033.00 36.24 23宁陈鸣男南京外国语学校高二1301101703057158.94 12015027.00 35.94 24常张吉鸿男江苏省常州高级中学高二60220155174525.65 18012030.00 35.65 25扬刘畅男江苏省扬州中学高一110803

12、1482693.36 20012032.00 35.36 26宁顾昱洲男南京树人国际学校初三80381351754285.35 2406030.00 35.35 27常邹晨男常州市第一中学高一8048471633384.23 2307030.00 34.23 28宁陈济宇男南京外国语学校高二015402403944.93 18011029.00 33.93 29苏倪泽堃男苏州外国语学校高一150268220385102312.79 1605021.00 33.79 30常刘敞男常州外国语学校初三2028111351942.43 19012031.00 33.43 31盐韩旭男大丰市初级中学初三

13、60236195545456.81 10016026.00 32.81 32盐潘成男大丰市初级中学初三60961022134715.89 15011026.00 31.89 33宁曹鹏程男南京市金陵中学高二7012826004585.73 1907026.00 31.73 34苏徐晔嘉男苏州中学高一090250413814.76 11015026.00 30.76 35常季雨阗男江苏省常州高级中学高二1101482302056938.66 220022.00 30.66 36宿胡运州男江苏省泗洪中学高二408241301932.41 2007027.00 29.41 37常徐磊男常州市正衡中学

14、初三603897372322.90 16010026.00 28.90 38常陈子旸男常州市正衡中学初三801181021704705.88 1607023.00 28.88 39常高胜寒男常州外国语学校初三1401181311665556.94 1308021.00 27.94 40常范静女常州市第一中学高一8046136473093.86 1806024.00 27.86 41常钱雨露女常州市第一中学高一301481271554605.75 1408022.00 27.75 42盐高贤达男大丰市初级中学初三701681421915717.14 1505020.00 27.14 43常陈中天

15、男江苏省常州高级中学高二40482451334665.83 9012021.00 26.83 44盐李鑫男江苏省大丰高级中学高一904861542533.16 11011022.00 25.16 45泰智天成男江苏省泰州中学高一60108157884135.16 1109020.00 25.16 46宁陈怡宁女南京外国语学校初二0114971113224.03 11010021.00 25.03 47淮王子旭男江苏省淮阴中学高一30128921033534.41 1307020.00 24.41 48泰韦正杰男江苏省泰州中学高一201061821164245.30 1108019.00 24.

16、30 49泰林霄竹女江苏省泰州中学高一10365701031.29 12010022.00 23.29 50盐蒋一瑶女大丰市初级中学初三6098721023324.15 1207019.00 23.15 51常于竟成男常州市第一中学高一70781271274025.03 1206018.00 23.03 52常吴昊男常州外国语学校初三2048116212052.56 1208020.00 22.56 53常孙珂男常州市第一中学高一5050571693264.08 1008018.00 22.08 54宿李达男江苏省泗洪中学高一409040972673.34 909018.00 21.34 55

17、淮胡凡男江苏省淮阴中学高一6012771853344.18 7010017.00 21.18 56扬刘文钊男江苏省扬州中学高一8012821913204.00 6011017.00 21.00 57宁何雨辰女南京树人国际学校初二8098137833984.98 6010016.00 20.98 58宁袁文韬男南京外国语学校初三30181010680.85 1703020.00 20.85 59宁蔡心瑗女南京外国语学校初三120901102212.76 1305018.00 20.76 60宁王立力男南京树人国际学校初三6078471703554.44 1402016.00 20.44 61宁周

18、围男南京外国语学校初三010215272523.15 1304017.00 20.15 62扬陈烨男江都中学高一604821503234.04 1105016.00 20.04 63常钱雨杰男常州外国语学校初三4028142302403.00 1007017.00 20.00 64常杨颢男江苏省常州高级中学高一200521632352.94 1007017.00 19.94 65宁黄宇韬男南师大附属中学高二506021101411.76 1206018.00 19.76 66常韩韵衡男江苏省常州高级中学高二5048175142873.59 808016.00 19.59 67常荀琳玲女常州市第

19、一中学高一4078531973684.60 608014.00 18.60 68泰田元景男泰州市二中附中初二50806601962.45 709016.00 18.45 69宁李耀东男南师大附属中学高二20601771774345.43 3010013.00 18.43 70盐李星男江苏省大丰高级中学高一208846822362.95 1104015.00 17.95 71常沈匡济男常州外国语学校初三4098132453153.94 806014.00 17.94 1常吴争锴男常州市第一中学高一2宁吴尚男南京外国语学校高二3宁陈实男南京外国语学校高一4盐倪昊斌男盐城市初级中学初三5常蒋中天男江

20、苏省常州高级中学高二6常陈爽女江苏省常州高级中学高二7常史鉴男江苏省常州高级中学高一8常刘启鹏男江苏省常州高级中学高二9常王凯南男江苏省常州高级中学高二10苏张若愚男苏州中学高二11宁贾志鹏男南京外国语学校初三12常杨宽男江苏省常州高级中学高二 13常王轩男江苏省常州高级中学高一 14常张昊男江苏省常州高级中学高二 以上85名选手获得JSOI2010第三轮选拔资格序市姓名性别学校名称年级Day1day2day3day4total折合1day5day6折合2总分72盐蒋畑宇男江苏省盐城中学高一0782201001.25 907016.00 17.25 73常高旺男常州市正衡中学初三3046523

21、41622.03 4011015.00 17.03 74宁崔文韬男金陵中学河西分校初三80903172082.60 905014.00 16.60 75宿伍艺女江苏省泗洪中学高二30300931531.91 509014.00 15.91 76盐莫宇宸男江苏省大丰高级中学高一304837731882.35 607013.00 15.35 77盐何玥女大丰市初级中学初二0108102242342.93 507012.00 14.93 78宁姜怀盼男南京市金陵中学高二000000.00 1004014.00 14.00 79泰孔令融男泰州市二中附中初三201601001033834.79 2070

22、9.00 13.79 80盐高飙男大丰市初级中学初三8070100172673.34 505010.00 13.34 81常干可雨男常州市第一中学高一4098142102903.63 30609.00 12.63 82宁陈莘莘男南京市金陵中学高一00220220.28 1002012.00 12.28 83淮李坚韧男江苏省淮阴中学高一202812601742.18 505010.00 12.18 84宁唐颀伟男南京树人国际学校初三3090181633644.55 0707.00 11.55 85盐张翔宇男大丰市初级中学初二202842341241.55 901010.00 11.55 86宁马

23、子喻女南京外国语学校初三1046110932593.24 20608.00 11.24 87淮严茂森男江苏省淮阴中学高二3078221332633.29 10607.00 10.29 88宁丁韵妍女南京外国语学校初二508646171992.49 7007.00 9.49 以上17名选手中高一以下的人员保留参加今年省夏令营集训的资格 执笔 张若愚指导 章维銑巨额奖金【问题描述】NJ市的快速发展得益于其便捷的交通。可是，随着经济的发展，大量的人进入NJ市，NJ市的交通也承受着巨大的压力。现在，NJ市正在筹划建设一个新型的交通枢纽，从而减轻交通的压力。NJ市包含n个区，有些区之间有双向的干道存在。

24、新型交通枢纽建设在这些干道的基础上，将其中的部分干道改进为新型干道。改进后，干道能承受的压力可以比原来增加几十倍。为了和谐发展，在新型的交通枢纽建成后，要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。政府已经预测出每条干道改进为新型干道的费用。政府希望建设新型交通枢纽的总费用最小，并以巨额奖金向市民征集方案。政府很快发现费用最小的方案不一定唯一，所以决定将奖金平分给每一种方案的第一个设计者，即如果一个人设计的费用是最小的而且前面没人和他设计出一模一样的方案，则他可获奖。Js08被奖金深深的吸引，准备设计一种方案。可是，他发现方案可能会很多，如果最后获奖者太多，巨额的资金分到每个人头

25、上的也不会太多。所以他决定先算一下可行的方案数是多少。输入输入的第一行包含两个数n (1 n 100)，m (1 m 1,000)，分别表示该市有多少个区和有多少条干道。接下来m行，每行三个数ai、bi、ci (1 ai, bi n, 1 ci 1,000,000,000)，表示ai区和bi区之间有一条干道，如果改进需要ci的费用。输入保证任何两个区之间至多有一条干道。对于任何一个费用c，不会有超过10条干道的费用都是c。输出输出费用最小的方案有多少种。由于答案可能很大，你只要输出方案数除以31011的模即可。时限 1s样例award.inaward.out4 61 2 11 3 11 4 1

26、2 3 22 4 13 4 18【问题分析】本题的求解任务可简述为求图的最小生成树个数，其中顶点数n=100，边数m=1000，对于任意一个边权ci不会有超过10条边权均为ci。输出总个数mod 31011。我们首先分析一组数据，把它的所有最小生成树都画出来：图1.1可以发现，上述的最小生成树都由一条权为1和两条权为2的边组成的。我们再手算一些数据，可以发现这么一个规律：对于某一张图所有的最小生成树，权值为ci的边的个数是个定值。利用这个规律，我们提出一个算法：先对图做一次最小生成树，确定各个权值ci的边的个数。然后按照kruskal的思路，由于边排序后相同权值的边是连续的一段，所以对于每一个

27、权值ci，我们可以进行2p的枚举（p为该权值的边的个数）得到其总的方案数ti，枚举完后，把这些边所连接的点变成连通的，再进行下一轮的枚举。最后按照乘法原理，把所有的ti乘起来，对31011取模，就是我们所要的答案。由于数据范围保证了p=10，所以2p的枚举不会超时。但是这个算法本身还有两个问题没有解决，一是为什么在枚举完某一权值的节点后，要把所有的边所连的点变成连通的？二是，为什么对于不同权值边的方案数，我们可以用乘法原理乘起来？其次，这个算法是基于我们发现的规律，那么我们发现的规律到底是否正确呢？下面的叙述将给出明确的回答：首先，生成树有如下的性质：对于一颗生成树，我们加入任意一条边，必然会

28、形成一个环。我们把环上的任意一条边删去，就可以得到一个新的生成树。考虑一张图G，仅保留最小权的边c，得到新图G，它不一定是连通的，可能是由几个连通分量组成，连通分量的点集分别为V1，V2。我们所要证明的就是，对于图G的任意一个最小生成树，其V1，V2对应的子图G1，G2必定是一颗树，并且都由边权为c的边组成。我们用反证法来证明：假如对于图G的某一个最小生成树，其子图Gi不是一棵树，而是若干个连通块，那么由于图G是连通的，所以我们可以确定Gi中的连通块必然通过若干条其他边连起来。那么此时我们将子图中某条可以将两个连通块连接起来的边加入图中（这条边必定可以找到，因为图G中，Gi为连通分量），这样图

29、G的最小生成树就会形成一个环，并且这个环上必定有权值比c大的边（因为必定有边将Gi与其他子图连接起来），这时我们去掉权值比c大的边，可以得到一颗新的生成树，而且这颗生成树比最小生成树还要小，这样就产生了矛盾。那么既然子图G1，G2为一棵树，那么权值为c的边的个数必定为定值，并且在选择完所有的权值为c的边后，这些边所连的点必定是连通的。我们将这些由c组成的连通块缩成一个点，得到一张新图G，可以得知图G的最小边，即图G的次小边，仍满足上述结论。由此，我们可以得知，从小到大确定各个边的情况，是互不影响的，满足使用乘法原理的性质。【算法实现】原问题算法的实现并不是特别复杂，唯一需要用到的高级数据结构是

30、就在合并点的连通性的时候需要使用并查集。在这里，我们介绍一个可以对没有p=10这个限制的求解的算法：基尔霍夫矩阵。基尔霍夫矩阵可以在n3的时间内算出一张图的生成树个数，用来代替原算法2p的枚举。而在本题的实现上有若干需要注意的地方：1.原算法的将点合并连通性必须改为将每一轮的连通块收缩成一个点，下一轮使用基尔霍夫矩阵计算时是对收缩后的图进行计算。但是具体实现的时候仍可以用并查集。2.收缩后的图会出现重边，不能简单的用boolean数组保存边，而对于自环需要去掉。3.由于基尔霍夫矩阵是计算行列式，高斯消元涉及实数运算，我们需要注意实数误差问题。4.关于这个算法的复杂度问题：虽然计算一次矩阵的复杂

31、度是O(n3)，而且看似要处理很多的矩阵（上限为n个），但是这个复杂度其实是很宽松的。由于每计算一次连通块，这个连通块就要被缩成一个点，如果连通块的大小是k，那么处理后的图的规模变化是-k+1。图最后被收缩成一个点，所以最多收缩n-1次（实际情况少的多），所以每次产生的额外规模最多为n。行列式的规模上限也为n（实际情况很小）。因此实际情况是比O(n4)小的很多，甚至比O(n3)小，最坏的情况就是所有边权都相等或者都不等，此时总复杂度为O(n3)。【知识拓展】并查集并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。并查集的

32、实现很简单，只需要用一个指针数组记fx录每个节点x的父亲节点，若fx=x则x为树根。查询两个节点是否在同一个集合，只要比较两个节点所在树的根节点是否相同。合并两棵树之需要把一棵树的根指向另一棵树的根即可。在实际应用中，一般还会加入路径压缩优化和启发式合并优化，使得查询与合并操作的时间复杂度为O(1)（实际的复杂度为反ackerman函数，其增长极为缓慢，接近于常数）。具体的实现代码如下：function father(x:longint):longint; /查询x所属集合,使用路径压缩优化begin if x=fx then exit(x); /为根 fx:=father(fx); /路径压

33、缩 exit(fx);end;procedure union(x,y:longint); /合并操作,使用启发式合并优化,rankx记录树的深度var x1,y1:longint;begin x1:=father(x); /分别找到所属集合 y1:=father(y); if rankx1=ranky1 then /深度相同 begin fy1:=fx1; inc(rankx1); /深度加1 end else begin if rankx1ranky1 then swap(x1,y1); /将深度小的树并到深度大的树中 fy1:=fx1; end;end;基尔霍夫矩阵基尔霍夫矩阵可以计算任意

34、一张图的生成树个数。其具体的实现方法如下：对于一张有n个顶点的图G，我们构造这么一个矩阵CG：1、 若ij，对于图G的vi，vj若有k条边相连（允许重边），则ci,j=-k，否则ci,j=0。2、 若i=j，则ci,j等于vi的度数。将矩阵C的第r行与第r列同时去掉，得到CG的任意一个n-1阶主子式CrG，其值的绝对值即为图G的生成树个数。行列式的计算可以用高斯消元，将其化为三角形行列式（形如图），计算对角线的乘积即为行列式的值。 上三角行列式 下三角行列式图1.2具体的代码实现如下：for i:=1 to n do /构造行列式 for j:=1 to n do begin inc(deti

35、,i,mapi,j); /计算vi的度数,注意图有重边,所以mapi,j保存边的个数 dec(deti,j,mapi,j); end;for i:=1 to n-1 do/高斯消元 begin for j:=i to n do if aj,i0 then /找到第i项非0的一行 begin for k:=1 to n do /将其交换至第i行 swap(ai,k,aj,k); break; end; for j:=i+1 to n do /将第i+1行至第n行分别消去第i项 begin t:=aj,i/ai,i; for k:=i to n do aj,k:=aj,k-ai,k*t; end;

36、 end;ans:=1;for i:=1 to n do ans:=ans*ai,i; /得到行列式的值由于矩阵的证明过于繁琐，并且涉及到高等数学，在此就不展开介绍，可以参见国家集训队2007年周冬的论文生成树的计数及其应用。【参考程序】C+参考程序：/ Program : Jsoi 2008 Award#include using namespace std;int w1001, a1001, b1001, s101, rank101;int goal101, first, last, n, m, tmp;void QSort(int head, int tail) / 排序 int i =

37、 head, j = tail, mid = w(i+j) 1; do while (wi mid) j -; if (i = j) swap(wi, wj), swap(ai, aj), swap(bi, bj), i +, j -; while (i = j); if (head j) QSort(head, j); if (i tail) QSort(i, tail); int Find_Set(int x) / 并查集基本操作find_set int res, t, backup; for (res = x; sres != res; res = sres); for (t = x;

38、st != t; t = backup) backup = st, st = res; return res; void Union(int a, int b) / 并查集基本操作union a = Find_Set(a), b = Find_Set(b); if (ranka rankb) sa = b; else sb = a, ranka += ranka = rankb; void Search(int now) if (now = last) / 所有的边都已经被搜索过了，开始判断连通性 int flag101 = 0, i; bool check; for (check = tru

39、e, i = 1; i = n; i +) / goal表示应该的连通性 if (flaggoali) if (flaggoali != Find_Set(i) check = false; break; else; else flaggoali = Find_Set(i); if (check) tmp = (tmp + 1) % 31011; return; int bak1101, bak2101; Search(now+1); / 不加入这个条边 memcpy(bak1, s, sizeof(s); / 加入这条边 memcpy(bak2, rank, sizeof(rank); if

40、 (Find_Set(anow) != Find_Set(bnow) Union(anow, bnow), Search(now+1); memcpy(s, bak1, sizeof(bak1); memcpy(rank, bak2, sizeof(bak2); int main() int bak1101, bak2101, ans101, i, j, t, total; freopen(award.in, r, stdin); freopen(award.out, w, stdout); scanf(%d%d, &n, &m); for (i = 1; i = m; i +) scanf(

41、%d%d%d, a+i, b+i, w+i); QSort(1, m); / 将边按照权值排序 for (i = 1; i = n; i +) si = i, ranki = 1; for (i = j = 1; i n; ansi = j, Union(aj, bj), i +) for ( ; j m) / 原来的图不连通，找不到最小生成树 printf(0n); return 0; for (i = 1; i = n; i +) si = i, ranki = 1; for (total = 1, i = 2; i = n; i +) for (t = i-1; i n & wansi = wansi-1; i +); / 在最小生成树的边中找到一段相同权值的边 memcpy(bak1, s, sizeo