图论补充习题.doc

NKOJ 1039: ArbitrageTime Limit: 1500 ms Memory Limit: 10000 kB Total Submit : 56(25 users)Accepted Submit : 29(24 users)Page View : 1456 Font Style: Aa Aa Aa Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent. Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not. InputThe input file will contain one or more test cases. Om the first line of each test case there is an integer n (1=n=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.OutputFor each test case, print one line telling whether arbitrage is possible or not in the format Case case: Yes respectively Case case: No.Sample Input3USDollarBritishPoundFrenchFranc3USDollar 0.5 BritishPoundBritishPound 10.0 FrenchFrancFrenchFranc 0.21 USDollar3USDollarBritishPoundFrenchFranc6USDollar 0.5 BritishPoundUSDollar 4.9 FrenchFrancBritishPound 10.0 FrenchFrancBritishPound 1.99 USDollarFrenchFranc 0.09 BritishPoundFrenchFranc 0.19 USDollar0Sample OutputCase 1: YesCase 2: NoNKOJ1784: Six Degrees of Cowvin BaconTime Limit: 1500 ms Memory Limit: 65536 kB Judge type: Multi-casesTotal Submit : 28(15 users)Accepted Submit : 15(14 users)Page View : 433 Font Style: Aa Aa Aa The cows have been making movies lately, so they are ready to play a variant of the famous game Six Degrees of Kevin Bacon. The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one degree away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two degrees away from each other (counted as: one degree to the cow theyve worked with and one more to the other cow). This scales to the general case. The N (2 = N = 300) cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made M (1 = M = 10000) movies and it is guaranteed that some relationship path exists between every pair of cows. Input* Line 1: Two space-separated integers: N and M * Lines 2.M+1: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., Mi); the subsequent Mi integers tell which cows were. Output* Line 1: A single integer that is 100 times the shortest mean degree of separation of any of the cows. Sample Input4 23 1 2 32 3 4Sample Output100NKOJ 1610: Play on WordsTime Limit: 1500 ms Memory Limit: 10000 kB Total Submit : 99(23 users)Accepted Submit : 23(17 users)Page View : 763 Font Style: Aa Aa Aa Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us. There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm can be followed by the word motorola. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door. InputThe input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 = N = 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters a through z will appear in the word. The same word may appear several times in the list.OutputYour program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times. If there exists such an ordering of plates, your program should print the sentence Ordering is possible. Otherwise, output the sentence The door cannot be opened. Sample Input32acmibm3acmmalformmouse2okokSample OutputThe door cannot be opened.Ordering is possible.The door cannot be opened.NKOJ其他图论基本题目1078、1755、1756、1559POJ图论基本题目1062、1125、1797、2253、1251、1258、1789、2485ACM竞赛须掌握的知识图论 路径问题 最短路径 0/1 边权最短路径 BFS 非负边权最短路径 Dijkstra u 可以用Dijkstra解决的问题的特征 负边权最短路径 Bellman-Ford u Bellman-Ford的Yen-氏优化 u 差分约束系统 Floyd u 广义路径问题 u 传递闭包 u 极小极大距离 / 极大极小距离 Euler Path / Tour 圈套圈算法 混合图的 Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path / Tour 构造 生成树问题 最小生成树 第k小生成树 最优比率生成树 u 0/1分数规划 度限制生成树 连通性问题 u 强大的DFS算法 无向图连通性 割点 割边 二连通分支 有向图连通性 强连通分支 u 2-SAT u 最小点基 有向无环图 拓扑排序 u 有向无环图与动态规划的关系 二分图匹配问题 u 一般图问题与二分图问题的转换思路 最大匹配 u 有向图的最小路径覆盖 u 0 / 1矩阵的最小覆盖 完备匹配 最优匹配 网络流问题 u 网络流模型的简单特征和与线性规划的关系 最大流最小割定理 最大流问题 有上下界的最大流问题 u 循环流 最小费用最大流 / 最大费用最大流 弦图的性质和判定 组合数学 u 解决组合数学问题时常用的思想 u 逼近