圖論補充習題

1、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 rate

2、s 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 dolla

3、r 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 ea

4、ch 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 ea

5、ch 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 valu

6、e 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.2

7、1 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  &

8、#160; 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 famo

9、us 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 nev

10、er 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 they've worked with and one more to the other cow). This scales to the general case. The N (2 <= N <= 300) cows are interested i

11、n 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 inte

12、gers: 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*

13、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 Sub

14、mit : 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. T

15、here 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&#

16、39;'. 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 give

17、n 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,

18、 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

19、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 sentenc

20、e "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競賽須掌握的知識圖論        路

21、徑問題               最短路徑                      0/1 邊權最短路徑 BFS             

22、0;        非負邊權最短路徑 Dijkstra u       可以用Dijkstra解決的問題的特征                      負邊權最短路徑 Bellman-Ford u      

23、 Bellman-Ford的Yen-氏優(yōu)化 u       差分約束系統(tǒng)                             Floyd u       廣義路徑問題 u   

24、    傳遞閉包 u       極小極大距離 / 極大極小距離 Euler Path / Tour        圈套圈算法        混合圖的 Euler Path / Tour Hamilton Path / Tour        特殊圖的Hamilton Path / Tour 構造 生成樹問題  

25、60;            最小生成樹                      第k小生成樹               最優(yōu)比率生成樹 u &#

26、160;     0/1分數(shù)規(guī)劃               度限制生成樹        連通性問題 u       強大的DFS算法               無向圖連通性 &

27、#160;                    割點 割邊 二連通分支               有向圖連通性              

28、0;       強連通分支 u       2-SAT u       最小點基 有向無環(huán)圖        拓撲排序 u       有向無環(huán)圖與動態(tài)規(guī)劃的關系 二分圖匹配問題 u       一般圖問題與二分圖問題的轉(zhuǎn)換思路 最大匹配

29、u       有向圖的最小路徑覆蓋 u       0 / 1矩陣的最小覆蓋        完備匹配        最優(yōu)匹配 網(wǎng)絡流問題 u       網(wǎng)絡流模型的簡單特征和與線性規(guī)劃的關系        最大流最小割定理  

30、      最大流問題 有上下界的最大流問題 u       循環(huán)流 最小費用最大流 / 最大費用最大流 弦圖的性質(zhì)和判定 組合數(shù)學 u       解決組合數(shù)學問題時常用的思想 u       逼近 u       遞推 / 動態(tài)規(guī)劃       

31、 概率問題        Polya 定理        計算幾何 / 解析幾何 u       計算幾何的核心：叉積 / 面積 u       解析幾何的主力：復數(shù) 基本形        點        直線，線段  

32、0;     多邊形 凸多邊形 / 凸包 u       凸包算法的引進，卷包裹法        Graham 掃描法 u       水平序的引進，共線凸包的補丁 完美凸包算法        相關判定          

33、0;    兩直線相交               兩線段相交               點在任意多邊形內(nèi)的判定               點在凸多邊形內(nèi)的判定  &

34、#160;            經(jīng)典問題               最小外接圓                      近似O(n)的最小外接圓算法  &

35、#160;            點集直徑                      旋轉(zhuǎn)卡殼，對踵點               多邊形的三角剖分 數(shù)學 / 數(shù)論 &#

36、160;      最大公約數(shù)               Euclid 算法                      擴展的Euclid算法       &

37、#160;                     同余方程 / 二元一次不定方程                           &#

38、160; 同余方程組        線性方程組               高斯消元法 u       解mod 2域上的線性方程組 u       整系數(shù)方程組的精確解法 矩陣        行列式的計算 u 

39、0;     利用矩陣乘法快速計算遞推關系        分數(shù)               分數(shù)樹               連分數(shù)逼近        數(shù)論計算  &#

40、160;            求N的約數(shù)個數(shù)               求phi(N)               求約數(shù)和         &#

41、160;                   素數(shù)問題               概率判素算法               概率因子分解 數(shù)據(jù)結(jié)構：        組織結(jié)構               二叉堆                      左偏樹          &