Yan2u's Blog

Description对于一张有向图，要你求图中最小圈的平均值是多少，即若一个圈经过k个节点，那么一个圈的平均值为圈上k条边权之和除以k，求其中的最小值。 Input第一行2个正整数，分别为n，m，表示有n个定点，m条边以下m行，每行3个整，分别代表一条边的起点，终点，权值。输入数据保证该图是连通的且存在圈。 Output一行一个数，表示最小圈的值，保留8位小数 Sample Input #11234564 51 2 52 3 53 1 52 4 34 1 3 Sample Output #113.66666667 Sample Input #21232 21 2 -2.92 1 -3.1 Sample Output #21-3.00000000 Sample Input #1 图示： graph LR d1((1));d2((2));d3((3));d4((4)) d1--5-->d2 d2--5-->d3 d3--5-->d1 d2--3-->d4 d4--3-->d1 最小圈如图，平均值为：3.66666667 graph ...

Description每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。 Input第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B） Output一个数，即有多少头牛被所有的牛认为是受欢迎的。 Sample Input12343 31 22 12 3 　输入样例图示： graph LR 1-->2 2-->1 2-->3 Sample Output11 分析用 $Tarjan$ 缩点方法解决这个题，因为在奶牛相互喜欢有向图网络中，每一个强连通分量里面的奶牛是最受欢迎的（上图中的 $(1,\;2)​$ 号奶牛） 求出所有的强连通分量后，原图将变成一个有向无环的 $DAG$ 图，也就是： graph LR 1-->2 2-->1 2-->3 发现 $3$ 号奶牛 ...

Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 Input输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。 Output输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组　　输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。 ...

Description在顺利攻破 Lord lsp 的防线之后，lqr 一行人来到了 Lord lsp 的城堡下方。Lord lsp 黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。现在 lqr 已经搞清楚黑暗城堡有 N 个房间，M 条可以制造的双向通道，以及每条通道的长度。 lqr 深知 Lord lsp 的想法， 为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的； 但是，为了尽量提高自己的移动效率，Lord lsp 一定会使得城堡满足下面的条件：设 Di 为如果所有的通道都被修建， 第 i 号房间与第 1 号房间的最短路径长度；而 Si 为实际修建的树形城堡中第 i 号房间与第1 号房间的路径长度，对于所有满足 1≤i≤N 的整数 i，有 Si = Di。为了打败 Lord lsp，lqr 想知道有多少种不同的城堡修建方案。于是 lqr 向 applepi 提出了这个问题。由于 applepi 还要忙着出模拟赛，所以这个任务就交给你了。当然，你只需要输出答案对 2^31 – 1 取模之后的结果就行了。 Inpu ...

跳转到在线页面 DescriptionHanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。 　　今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在 Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数x满足： 　　1、x和a0的最大公约数是a1； 　　2、x和b0的最小公倍数是b1。 　　Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。 Input第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。 Output共n行。每组输入数据的输出结果占一行，为一个整数。 ...

Description约翰叔叔希望能够廉价连接他的供水系统，但是他不希望他的竞争对手知道他选择的路线。一般这样的问题需要选择最便宜的方式，所以他决定避免这种情况而采用第二便宜的方式。 现在有W(3 <= W <= 2000)个供水站，其中最多有P(P <=20,000)< span=”“>条管道，每一条管道连接了两个水站，并且不存在一条管道连接同一个水站，两个水站之间最多只有一条管道。每条管道有一定的费用。请寻找第二便宜的连接方式，使所有的水站相连。 假设最便宜的方案有且只有一种，并且至少有两种可行的连接方案。所有的费用都不超过16位有符号整数。水站用1到W的自然数表示 Input第一行：两个数W和P 第2～P+1行：每行描述了一条管道，有3个用空格分开的整数，前两个数表示管道连接的两个端点。第3个数是管道的费用 Output仅一行，第二便宜的管道铺设费用 Sample Input123456785 7 1 2 3 2 3 4 1 4 7 2 4 11 2 5 9 5 4 5 3 5 8 输入数据图示： graph LR 1--3---2 2- ...

Description给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。 Input第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。 Output一行表示所求生成树的边权和。 Sample Input1232 2 10 1 1 10 1 2 0 图示： graph LR 0--"1(black)"---1 0--"2(white)"---1 Sample Output12 分析这道题要用到二分法，对 $Kruskal$ 算法进行变形，首先我们在对边集排序时，要让值相等的情况下白色边在前（为了选边做准备），然后为了影响 $Kruskal$ 的选边过程，对所有的白色边加上一个权值，这个权值可正可负，这是因为将编边集数组排序时： 附加权为正时，表示当前的白色边过多，我们让权值较大的白色边再大一点，就可以被$Kruskal$ 算法排除在最小生成树外面，达到少选的目的 附加权为 ...

DescripitonZ小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。 Z小镇附近共有N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。 频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。 Input第一行包含两个正整数，N和M。 接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。 Output第一行包含两个正整数，N和M。 接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。 Samples # Input ...

Description现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。 Input第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。　　 接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。　　 注意：具有相同权值的边不会超过10条。 Output输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。 Sample Input12345674 61 2 11 3 11 4 12 3 22 4 13 4 1 Sample Output18 Sample Input 图示： graph LR 1--1---2 1--1---3 1-- ...

Description北极地区共有P座村庄，每座村庄均有自己的坐标。现在决定在村庄之间建立通信网络，其中通讯工具可以是无线电收发机，也可以是卫星设备。你的任务是让任意两座村庄之间都可以直接或间接地通信。卫星设备一共有S台，拥有卫星设备的两座村庄之间无论相距多远都可以直接通信；其他每个村庄都可以配备一台无线收发机，但必须具有相同的参数d。只有欧基里德不是超过d的村庄才能用无线收发机直接通讯。由于d越大的无线电收发机越贵，你需要合理分配这S台卫星设备，才能让其他村庄的无线电收发机的d最小。 Input第一行为整数S,P，表示卫星通信设备数目和村庄数目。接下来的P行，每行表示一个村庄的坐标(x,y)。 Output输出一个保留2位小数的实数，表示最小的无线电收发器半径。 Sample Input12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747 ...