UVa 10199 Tourist Guide

題意：
    LuckyCat中文翻譯，基本上就是求所有Cut Vertex。

想法：
    Cut Vertex模板。

POJ 1523 SPF

題意：
    基本上就是給你一個Network的Graph，然後求這graph的所有割點，以及如果去除掉該割點能將Network分成幾個部分。
    本題都是雙向邊，且每個測資是以1個0分開，最後結束也是1個0。

想法：
    Cut Vertex模板。

UVa 247 Calling Circles

題意：
    LuckyCat中文翻譯
想法：
    SCC Tarjan演算法模板，將每個SCC的朋友名字都存下來，然後一行一行輸出。

UVa 11838 Come and Go

題意：
    題目求這個城市是否為一個強連通的城市(從任意點出發可以抵達每個點)，第一行會給N個點和M條路，底下M行每行有V,W,P，如果P==1表示該條路為單向V->W，P==2則是雙向V<->W。

想法：
    SCC模板，檢查scc_cnt是否為1，因為scc_cnt==1表示整個graph都可連通。

UVa 315 & POJ 1144 Network

題意：
    critical point指的是在一個connected graph中，如果移除該點，會使得該graph不再connected，則該點為critical point(cut vertex，割點)，現在給你一個graph，求critical point的數量。
    給你一個N表示共有N個點，底下最多N行，以0表示本次case輸入完畢，每行有a,b1,b2,b3.....，表示(a,b1),(a,b2),(a,b3)為邊，記得建邊的時候為雙向。

想法：
     cut vertex模板題 。

UVa 10080 Gopher II

題意：
    有N個地鼠和M個地鼠洞，每個點都有座標(x,y)，因此每隻地鼠和每個地鼠洞之間有不同的距離，每隻地鼠的移動速度都是v，現在有老鷹會在s秒後抓沒有跑進洞的地鼠，一個地鼠洞只能藏一隻地鼠，求沒有躲到洞裡被老鷹抓走的地鼠的最少數量為?

想法：
    地鼠在左邊，地鼠洞在右邊，把每隻地鼠與能在時間內跑到的地鼠洞都建一條邊，然後做最大匹配，答案就是(地鼠數量-最大匹配數)。

UVa 1194 & POJ 1325 Machine Schedule

題意：
    有A,B兩台機器，A的mode從0~n-1，B的mode從0~m-1，現在有k個job，底下有k行，每行有三個數i,x,y表示第i個job，A機器需用mode(x)完成這項工作，B機器則是需用mode(y)，一向工作只需交給A或B其中一個即可。有個規則是A,B這兩台機器變換mode的時候需要restart一次，例如mode(1)變成mode(10)需要restart一次，一開始兩台機器都是從mode(0)開始，問如何分配工作給A或B使得總restart次數最小，並輸出restart次數。

想法：
    一件工作x,y如果選x則不用y，反之選y就不用x，但都是要restart一次，因此可以想到最大匹配數，如果x或y其中一個已經匹配好了，表示A或B其中之一已經restart一次，則這件job就可以跳過。
    具體做法是，將第i個工作x放到左邊那群，y放到右邊那群，並建立(x,y)這條邊，然後套模板求最大匹配數就是答案。注意讀入測資的時候如果x或y其中是0，則直接跳過不用建邊，因為機器從mode(0)開始。

UVa 663 & POJ 1486 Sorting Slides

想法：
    做最大匹配，做完可從llink[i]=j得到每條匹配的邊(i,j)，也就是(i,j)是可能的答案，但要確認這條邊(i,j)的唯一性。
    例如Sample Input的第二個測資，做完最大匹配可得到(A,1)(B,2)兩條邊，最大匹配數為2，要確認(A,1)是否唯一，就把(A,1)這條邊去掉並且禁止，然後再做一次最大匹配，會變成得到(A,2)(B,1)，最大匹配數還是2，與數量原來一樣並沒有減少，因此可知(A,1)這條邊不唯一。同理(B,2)也把它去掉並禁止，再做一次最大匹配，如果最大匹配數比原本小，這條邊就是答案可以輸出，反之如果最大匹配數和原本一樣，則這條邊不唯一不能輸出。
    從底下code可以看到最大匹配的模板函數Bipartite(int n, int u, int v)多了兩個參數u, v，表示做最大匹配的時候禁止(u,v)這條邊的使用(line 65)。

UVa 10349 Antenna Placement

題意：
    如題目的圖，一個圓圈最多能圈住兩個'*'，現在問一幅圖有n個'*'，最少用多少個圓圈就能把所有'*'圈住？

想法：
    最大匹配問題，將圖上所有點分成兩群相間隔，例如
101010
010101
101010
    在編號1的'*'建一條邊連到S(Super Source)，在編號'0'的'*'建一條邊連到T(Super Sink )，然後相鄰的'*'彼此也建一條邊，這些邊的容量都是1，建完邊後套一次最大流模板，就是最大匹配數。
    做最大匹配得到的結果不是真正的答案，例如*****五個'*'的最大匹配是2，答案則是(5-3)，因此本題答案為(所有'*'數量-最大匹配數)。

POJ 1742 Coins

題意：
    有N種硬幣，每種硬幣價值A[i]元以及該種硬幣的數量為C[i]，問這些硬幣在最多總合為M元的限制下有幾種組合數?

想法：
    01背包，dp[i]=true表示i元可以被組合出來，最後看dp[1]~dp[M]有幾個true就是答案。這題時間限制嚴格，因此用POJ 1276那篇的方法還是會TLE，因此在底下code22行，我們知道如果j是從M~0表示一次放一個物品，每種要做C[i]次，現在22行j從0開始~M，是用無限背包的方式，先把物品當作無限個，類似greedy的方式，然後用個num陣列來計數，這樣每種物品都只要跑1次就可以了。