Drainage Ditches Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16292 Accepted Submission(s): 7737 Problem Description Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. 继续阅读 >>

余海 17/02/09 21:43:45
Flow Problem Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 14791 Accepted Submission(s): 6960 Problem Description Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph. Input The first line of input contains an integer T, denoting the number of test cases. For each test case, the first line contains two integers N and M, d 继续阅读 >>

余海 17/02/09 19:56:38
Heavy Transportation Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 32337 Accepted: 8567 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight. Fortunately he already has a plan of the c 继续阅读 >>

余海 17/02/08 21:38:58
Frogger Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40814 Accepted: 13096 Description Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stone 继续阅读 >>

余海 17/02/08 18:28:46
Til the Cows Come Home Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 48111 Accepted: 16379 Description Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible. Farmer John’s field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple t 继续阅读 >>

余海 17/02/08 16:23:41
还是畅通工程 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。 当N为0时,输入结束,该用例不被处理。 Output 对每个测试用例,在1行里输出最小的公路总长度。 Sample Input 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 Sample Output 3 5 简单模板题 #include<iostream> #include<cstdio> #include<stri 继续阅读 >>

余海 17/02/07 13:18:41
模板题: fzu2087 统计树边 解法(mengxiang000000的博客 ) 思路:用kruskal算法模拟生成树的过程。同时也是一个贪心生成树的过程,我们知道,生成的树的边权值和是一定的,那么对于边的替换的值也是能够确定的:只有权值相同的边才有可能是另一种生成树方法的边。 然后我就呆萌的记录有多少重边权值的边,然后加上n-1,开开心心的提交,实力WA。一组数据就可以干掉我: 3 3 1 2 1 1 2 2 2 3 1 所以记得一定不要跟我犯一样的错误,我们需要的是动态判断一条边权值相同的边能否可能是另一种生成树方法的边。我们直接在kruskal算法过程中加上动态判断的成分就可以了,那么要如何判断呢?遍历每一条边的时候,如果有相同权值的边,像kruskal一样的判断条件,判断这条边能否加入生成树中即可。 kruskal算法判断一条边是否能够贪心的加入生成树中: for(int i=0;i<m;i++) { if(find(a[i].x)!=find(a[i].y)) { zh 继续阅读 >>

余海 17/02/07 12:57:58
畅通工程再续 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 26109 Accepted Submission(s): 8459 Problem Description 相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。 Input 输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。 每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下 继续阅读 >>

余海 17/02/07 12:33:25
Jungle Roads Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 24836 Accepted: 11691 Description The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads 继续阅读 >>

余海 17/02/07 12:30:40
Network Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 16497 Accepted: 6545 Special Judge Description Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hu 继续阅读 >>

余海 17/02/07 00:41:08