期望得分：100+100+100=300
實際得分：70+40+20=130
T1 [SCOI2007]kshort弱化版
有n個城市和m條單向道路，城市編号為1~n。每條道路連接配接兩個不同的城市，且任意兩條道路要麼起點不同要麼終點不同，是以n和m滿足m<=n(n-1)。給定兩個城市a和b，可以給a到b的所有簡單路（所有城市最多經過一次，包括起點和終點）排序：先按長度從小到大排序，長度相同時按照字典序從小到大排序。你的任務是求出a到b的第k短路。
輸入第一行包含五個正整數n, m, k, a, b。以下m行每行三個整數u, v, l，表示從城市u到城市v有一條長度為l的單向道路。100%的資料滿足：2<=n<=50, 1<=k<=200
如果a到b的簡單路不足k條，輸出No，否則輸出第k短路：從城市a開始依次輸出每個到達的城市，直到城市b，中間用減号"-"分割。
基本思路：A*跑k短路，二進制壓縮判重
考場思路：重載運算符比較字典序
錯因：spfa判重數組vis，用了邊權數組val
另一種方式：記錄所有長度<=第k短長度的路徑，取第k條
記錄路徑的時候，定義vector<結構體>，直接sort
vector是從0開始的！！！！
View Code
T2[ZJOI2007]最大半連通子圖
一個有向圖G=(V,E)稱為半連通的(Semi-Connected)，如果滿足：?u,v∈V，滿足u→v或v→u，即對于圖中任意
兩點u，v,存在一條u到v的有向路徑或者從v到u的有向路徑。若G'=(V',E')滿足V'?V，E'是E中所有跟V'有關的邊，
則稱G'是G的一個導出子圖。若G'是G的導出子圖，且G'半連通，則稱G'為G的半連通子圖。若G'是G所有半連通子圖
中包含節點數最多的，則稱G'是G的最大半連通子圖。給定一個有向圖G，請求出G的最大半連通子圖擁有的節點數K
，以及不同的最大半連通子圖的數目C。由于C可能比較大，僅要求輸出C對X的餘數。
第一行包含兩個整數N，M，X。N，M分别表示圖G的點數與邊數，X的意義如上文所述接下來M行，每行兩個正整
數a, b，表示一條有向邊(a, b)。圖中的每個點将編号為1,2,3…N，保證輸入中同一個(a,b)不會出現兩次。N ≤1
00000, M ≤1000000；對于100%的資料， X ≤10^8
應包含兩行，第一行包含一個整數K。第二行包含整數C Mod X.
tarjan縮環，然後拓撲排序求最長鍊
注意縮環之後重新構圖會出現重邊，在拓撲排序裡計算方案數時會多算
是以拓撲排序時判斷一下是否被同一節點重複更新
錯因：沒有想到重邊，存邊的數組大小與點混淆
T3[AHOI2006]上學路線route
可可和卡卡家住合肥市的東郊，每天上學他們都要轉車多次才能到達市區西端的學校。直到有一天他們兩人參加了學校的資訊學奧林匹克競賽小組才發現每天上學的乘車路線不一定是最優的。 可可：“很可能我們在上學的路途上浪費了大量的時間，讓我們寫一個程式來計算上學需要的最少時間吧！” 合肥市一共設有N個公共汽車站，不妨将它們編号為1…N的自然數，并認為可可和卡卡家住在1号汽車站附近，而他們學校在N号汽車站。市内有M條直達汽車路線，執行第i條路線的公共汽車往返于站點pi和qi之間，從起點到終點需要花費的時間為ti。(1<=i<=M, 1<=pi, qi<=N) 兩個人坐在電腦前，根據上面的資訊很快就程式設計算出了最優的乘車方案。然而可可忽然有了一個鬼點子，他想趁卡卡不備，在卡卡的輸入資料中删去一些路線，進而讓卡卡的程式得出的答案大于實際的最短時間。而對于每一條路線i事實上都有一個代價ci：删去路線的ci越大卡卡就越容易發現這個玩笑，可可想知道什麼樣的删除方案可以達到他的目的而讓被删除的公共汽車路線ci之和最小。 [任務] 編寫一個程式： 從輸入檔案中讀取合肥市公交路線的資訊； 計算出實際上可可和卡卡上學需要花費的最少時間； 幫助可可設計一個方案，删除輸入資訊中的一些公交路線，使得删除後從家到學校需要的最少時間變大，而被删除路線的ci和最小；向輸出檔案輸出答案。
輸入檔案中第一行有兩個正整數N和M，分别表示合肥市公共汽車站和公交汽車路線的個數。以下M行，每行（第i行，總第(i+1)行）用四個正整數描述第i條路線：pi, qi, ti, ci；具體含義見上文描述。
輸出檔案最多有兩行。 第一行中僅有一個整數，表示從可可和卡卡家到學校需要的最短時間。 第二行輸出一個整數C,表示Ci之和
思路：找出所有的最短路，重建立圖，跑最小割
錯因：
确定這條邊在最短路上：
正确方法：dis[s,u]+w+dis[v,t]=dis[s,t]
錯誤方法：從t開始枚舉，dis[1,u]+w=dis[1,v]，隻是計算了1到某個點的最短路
作者：xxy
本文版權歸作者所有，轉載請用連結，請勿原文轉載，Thanks♪(･ω･)ﾉ。