图论

Counting Leaves(PATA-1004) 题面 A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. 输入 Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format: 1ID K ID[1] ID[2] ... ID[K] where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01. ...

Emergency(PATA-1003) 题面 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible. ...

简介 Johnson算法是求解多源最短路的算法之一，核心操作是re-weight，适用于不包含负环（负权回路）的图。时间复杂度$O(nm+nmlogm)$。 ...

简介 Floyd-Warshall算法是求解多源最短路的算法之一，核心思想是动态规划，适用于不包含负环（负权回路）的图。时间复杂度$O(n^{3})$，空间复杂度$O(n^{2})$。 ...

简介 Bellman-Ford算法是求解单源最短路的算法之一，适用于可包含负边权的有向和无向图，可以判断是否包含负环（注意，如果是包含负权回路则不存在最短路问题）。时间复杂度$O(nm)$。 ...

简介 Dijkstra算法是求解单源最短路的算法之一，核心思想是贪心，只适用于边权为正的无向和有向图。原复杂度$O(n^{2})$，优化后时间复杂度能到$O(mlog_{m})$。 ...

Hawk-and-Chicken (HDU - 3639) 题面 Kids in kindergarten enjoy playing a game called Hawk-and-Chicken. But there always exists a big problem: every kid in this game want to play the role of Hawk. So the teacher came up with an idea: Vote. Every child have some nice handkerchiefs, and if he/she think someone is suitable for the role of Hawk, he/she gives a handkerchief to this kid, which means this kid who is given the handkerchief win the support. Note the support can be transmitted. Kids who get the most supports win in the vote and able to play the role of Hawk.(A note:if A can win support from B(A != B) A can win only one support from B in any case the number of the supports transmitted from B to A are many. And A can’t win the support from himself in any case. If two or more kids own the same number of support from others, we treat all of them as winner. Here’s a sample: 3 kids A, B and C, A gives a handkerchief to B, B gives a handkerchief to C, so C wins 2 supports and he is choosen to be the Hawk. ...

Summer Holiday (HDU - 1827) 题面 To see a World in a Grain of Sand And a Heaven in a Wild Flower, Hold Infinity in the palm of your hand And Eternity in an hour. —— William Blake 听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？ ...

Proving Equivalences (HDU - 2767) 题面 Consider the following exercise, found in a generic linear algebra textbook. Let A be an n × n matrix. Prove that the following statements are equivalent: \1. A is invertible. \2. Ax = b has exactly one solution for every n × 1 matrix b. \3. Ax = b is consistent for every n × 1 matrix b. \4. Ax = 0 has only the trivial solution x = 0. ...

Jungle Roads (POJ - 1251) 题面 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 in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems. ...

迷宫城堡 (HDU - 1269) 题面 为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。 ...