JSOI 巨额奖金.docVIP

执笔 张若愚 指导 章维銑 巨额奖金 【问题描述】 NJ市的快速发展得益于其便捷的交通。可是，随着经济的发展，大量的人进入NJ市，NJ市的交通也承受着巨大的压力。现在，NJ市正在筹划建设一个新型的交通枢纽，从而减轻交通的压力。 NJ市包含n个区，有些区之间有双向的干道存在。新型交通枢纽建设在这些干道的基础上，将其中的部分干道改进为新型干道。改进后，干道能承受的压力可以比原来增加几十倍。为了和谐发展，在新型的交通枢纽建成后，要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。政府已经预测出每条干道改进为新型干道的费用。政府希望建设新型交通枢纽的总费用最小，并以巨额奖金向市民征集方案。政府很快发现费用最小的方案不一定唯一，所以决定将奖金平分给每一种方案的第一个设计者，即如果一个人设计的费用是最小的而且前面没人和他设计出一模一样的方案，则他可获奖。 Js08被奖金深深的吸引，准备设计一种方案。可是，他发现方案可能会很多，如果最后获奖者太多，巨额的资金分到每个人头上的也不会太多。所以他决定先算一下可行的方案数是多少。 输入 输入的第一行包含两个数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.in award.out 4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1 8 【问题分析】 本题的求解任务可简述为求图的最小生成树个数，其中顶点数n=100，边数m=1000，对于任意一个边权ci不会有超过10条边权均为ci。输出总个数mod 31011。 我们首先分析一组数据，把它的所有最小生成树都画出来： 图1.1 可以发现，上述的最小生成树都由一条权为1和两条权为2的边组成的。 我们再手算一些数据，可以发现这么一个规律：对于某一张图所有的最小生成树，权值为ci的边的个数是个定值。利用这个规律，我们提出一个算法： 先对图做一次最小生成树，确定各个权值ci的边的个数。然后按照kruskal的思路，由于边排序后相同权值的边是连续的一段，所以对于每一个权值ci，我们可以进行2^p的枚举（p为该权值的边的个数）得到其总的方案数ti，枚举完后，把这些边所连接的点变成连通的，再进行下一轮的枚举。最后按照乘法原理，把所有的ti乘起来，对31011取模，就是我们所要的答案。 由于数据范围保证了p=10，所以2^p的枚举不会超时。 但是这个算法本身还有两个问题没有解决，一是为什么在枚举完某一权值的节点后，要把所有的边所连的点变成连通的？二是，为什么对于不同权值边的方案数，我们可以用乘法原理乘起来？其次，这个算法是基于我们发现的规律，那么我们发现的规律到底是否正确呢？下面的叙述将给出明确的回答： 首先，生成树有如下的性质：对于一颗生成树，我们加入任意一条边，必然会形成一个环。我们把环上的任意一条边删去，就可以得到一个新的生成树。 考虑一张图G，仅保留最小权的边c，得到新图G’，它不一定是连通的，可能是由几个连通分量组成，连通分量的点集分别为V1，V2……。我们所要证明的就是，对于图G的任意一个最小生成树，其V1，V2对应的子图G1，G2……必定是一颗树，并且都由边权为c的边组成。 我们用反证法来证明：假如对于图G的某一个最小生成树，其子图Gi不是一棵树，而是若干个连通块，那么由于图G是连通的，所以我们可以确定Gi中的连通块必然通过若干条其他边连起来。那么此时我们将子图中某条可以将两个连通块连接起来的边加入图中（这条边必定可以找到，因为图G’中，Gi为连通分量），这样图G的最小生成树就会形成一个环，并且这个环上必定有权值比c大的边（因为必定有边将Gi与其他子图连接起来），这时我们去掉权值比c大的边，可以得到一颗新的生成树，而且这颗生成树比最小生成树还要小，这样就产生了矛盾。 那么既然子图G1，G2……为一棵树，那么权值为c的边的个数必定为定值，并且在选择完所有的权值为c的边后，这些边所连的点必定是连通的。我们将这些由c组成的连通块缩成一个点，得到一张新图G’’，可以得知图G’’的最小边，即图G的次小边，仍满足上述结论。由此，我们可以得知，从小到大确定各个边的情况，是互不影响的，满足使用乘法原理的性质。 【算法实现】 原问题算法的实现并不是特别复杂，唯一需要用到的