Dijkstra with STL priority_queue 優先隊列

Dijkstra算法是一個經典的求單源最短路的算法，經過堆優化的Dijkstra算法有着良好的性能，雖然Heap的代碼複雜度並不算很高，但是至少也會爲程序的調試帶來一些麻煩。現在C++ STL開放了，所以可以用STL中的PQ容器（優先級隊列）來實現堆。

例題：

【題目描述】

在某個遙遠的國家裏，有n個城市。編號爲1，2，3，……，n。

這個國家的政府修建了m條雙向的公路。每條公路連接着兩個城市。沿着某條公路，開車從一個城市到另一個城市，需要花費一定的汽油。

開車每經過一個城市，都會被收取一定的費用（包括起點和終點城市）。所有的收費站都在城市中，在城市間的公路上沒有任何的收費站。

小紅現在要開車從城市u到城市v(1<=u，v<=n)。她的車最多可以裝下s升的汽油。在出發的時候，車的油箱是滿的，並且她在路上不想加油。

在路上，每經過一個城市，她要交一定的費用。如果她某次交的費用比較多，她的心情就會變得很糟。所以她想知道，在她能到達目的地的前提下，她交的費用中最多的一次最少是多少。這個問題對於她來說太難了，於是她找到了聰明的你，你能幫幫她嗎？

【輸入格式】

第一行5個正整數，n，m，u，v，s。分別表示有n個城市，m條公路，從城市u到城市v，車的油箱的容量爲s升。

接下來有n行，每行1個正整數，fi。表示經過城市i，需要交費fi元。

再接下來有m行，每行3個正整數，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之間有一條公路，如果從城市ai到城市bi，或者從城市bi到城市ai，需要用ci升汽油。

【輸出格式】

僅一個整數，表示小紅交費最多的一次的最小值。

如果她無法到達城市v，輸出-1。

【輸入樣例1】

4 4 2 3 8

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例1】

8

【輸入樣例2】

4 4 2 3 3

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例2】

-1

【數據規模】

對於60%的數據，滿足n<=200，m<=10000，s<=200

對於100%的數據，滿足n<=10000，m<=50000，s<=1000000000

對於100%的數據，滿足ci<=1000000000，fi<=1000000000，可能有兩條邊連接着相同的城市。

[分析]

這道題是道判定類題目，算法是二分答案+單源最短路。

由於數據很大，二分N+SPFA會超時1組，所以考慮Dijkstra+Heap。

[我的代碼]

C++语言: Codee#25838

001 /*
002 *Problem: NOIP模擬題 收費站
003 *Author: YeefanZhu
004 *Website: www.yeefanblog.tk
005 *GTalk: zyfworks@gmail.com
006 */
007 #include <cstdio>
008 #include <vector>
009 #include <cstdlib>
010 #include <algorithm>
011 #include <queue>
012 using namespace std;
013 const int MAXN=10001;
014 const int INF=1100000000;
015 int Cost[MAXN],BS[MAXN];
016 int N,M,S,B,E;
017 vector<int> Map[MAXN];
018 vector<int>Val[MAXN];
019
020 inline void init()
021 {
022     scanf("%d %d %d %d %d\n",&N,&M,&B,&E,&S);
023     for(int i=1;i<=N;i++)
024     {
025         scanf("%d\n",&Cost[i]);
026         BS[i]=Cost[i];
027     }
028     sort(BS+1,BS+N+1);
029     int a,b,v;
030     for(int i=1;i<=M;i++)
031     {
032         scanf("%d %d %d\n",&a,&b,&v);
033         Map[a].push_back(b);
034         Map[b].push_back(a);
035         Val[a].push_back(v);
036         Val[b].push_back(v);
037     }
038 }
039
040 priority_queue<pair<int,int> > PQ;
041 int Used[MAXN];
042 int Dist[MAXN];
043
044 inline bool SP(int x)
045
046 {
047     if(Cost[B]>x) return false;
048     for(int i=1;i<=N;i++) {Used[i]=0,Dist[i]=INF;}
049     Dist[B]=0;
050     PQ.push(make_pair(0,B));
051     int u,v,cost;
052     while(!PQ.empty())
053     {
054         u=PQ.top().second;
055         PQ.pop();
056         if(!Used[u])
057         {
058             Used[u]=1;
059             for(unsigned int i=0;i<Map[u].size();i++)
060             {
061                 v=Map[u][i];
062                 cost=Val[u][i];
063                 if(Cost[v]>x) continue;
064                 if(!Used[v]&&Dist[v]-Dist[u]>cost)
065                 {
066                     Dist[v]=Dist[u]+cost;
067                     PQ.push(make_pair(-Dist[v],v));
068                 }
069             }
070         }
071     }
072     if(Dist[E]>S) return false;
073     return true;
074 }
075
076 inline void solve()
077 {
078     int L=1,R=N;
079     int Mid;
080     if(!SP(BS[N])) {printf("-1\n");return;}
081     int Ans;
082     bool flag;
083     while(L<=R)
084     {
085         Mid=(L+R)>>1;
086         flag=SP(BS[Mid]);
087         if(flag)
088         {
089             Ans=BS[Mid];
090             R=Mid-1;
091         }
092         else L=Mid+1;
093     }
094     printf("%d\n",Ans);
095 }
096
097 int main()
098 {
099     freopen("cost.in","r",stdin);
100     freopen("cost.out","w",stdout);
101     init();
102     solve();
103     return 0;
104 }

【轉載】淺談2—SAT問題

2-SAT：http://www.cppblog.com/ACflying/archive/2009/06/06/86912.html

1 2 - SAT就是2判定性問題，是一種特殊的邏輯判定問題。
2 2 - SAT問題有何特殊性？該如何求解？
3 我們從一道例題來認識2 - SAT問題，並提出對一類2 - SAT問題通用的解法。 

Poi  0106  Peaceful Commission [和平委員會]：

某國有n個黨派，每個黨派在議會中恰有2個代表。
現在要成立和平委員會 ，該會滿足：
每個黨派在和平委員會中有且只有一個代表
如果某兩個代表不和，則他們不能都屬於委員會
代表的編號從1到2n，編號為2a - 1 、2a的代表屬於第a個黨派

輸入n（黨派數），m（不友好對數）及m對兩兩不和的代表編號
其中1≤n≤ 8000 ， 0 ≤m ≤ 20000
 
求和平委員會是否能創立。若能，求一種構成方式。
輸入：     輸出：3   2         1       1   3         4         2   4         5               

原題可描述為：

有n個組，第i個組裡有兩個節點Ai, Ai '  。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。
（在這裡把Ai, Ai '  的定義稍稍放寬一些，它們同時表示屬於同一個組的兩個節點。也就是說，如果我們描述Ai，那麼描述這個組的另一個節點就可以用Ai ' ）

初步構圖
如果Ai與Aj不相容，那麼如果選擇了Ai，必須選擇Aj‘ ；同樣，如果選擇了Aj，就必須選擇Ai’ 。   Ai             Aj ' 
 Aj             Ai‘                    
這樣的兩條邊對稱

我們從一個例子來看：
假設4個組，不和的代表為：1和4，2和3，7和3，那麼構圖：
假設：首先選1 3必須選，2不可選 8必須選， 4 、7不可選  5 、6可以任選一個

矛盾的情況為：
存在Ai，使得Ai既必須被選又不可選。

得到演算法1：
枚舉每一對尚未確定的Ai, Ai‘ ，任選1個，推導出相關的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。
此演算法正確性簡要說明：
由於Ai,Ai '  都是尚未確定的，它們不與之前的組相關聯，前面的選擇不會影響Ai, Ai '  。
演算法的時間複雜度在最壞的情況下為O(nm)。
在這個演算法中，並沒有很好的利用圖中邊的對稱性

 更一般的說：
在每個一個環裡，任意一個點的選擇代表將要選擇此環裡的每一個點。不妨把環收縮成一個子節點（規定這樣的環是極大強連通子圖）。新節點的選擇表示選擇這個節點所對應的環中的每一個節點.對於原圖中的每條邊Ai -> Aj（設Ai屬於環Si，Aj屬於環Sj）如果Si≠Sj，則在新圖中連邊:Si -> Sj

這樣構造出一個新的有向無環圖。此圖與原圖等價。

通過求強連通分量，可以把圖轉換成新的有向無環圖，在這個基礎上，介紹一個新的演算法。

新演算法中，如果存在一對Ai, Ai ' 屬於同一個環，則判無解，否則將採用拓撲排序，以自底向上的順序進行推導，一定能找到可行解。

至於這個演算法的得來及正確性，將在下一段文字中進行詳細分析。
回憶構圖的過程：
對於兩個不相容的點 Ai, Aj，構圖方式為：Ai -> Aj ' ,Aj->Ai ' ,前面提到過，這樣的兩條邊對稱，也就是說：
如果存在Ai -> Aj，必定存在Aj ' ->Ai ' 。
等價於：Ai -> Ak,Ak ' ->Ai '  方便起見，之後“ -> ”代表這樣一種傳遞關係.

猜測1：圖中的環分別對稱
如果存在Ai,Aj，Ai,Aj屬於同一個環(記作Si),那麼Ai ' , Aj ' 也必定屬於一個環(記作Si ' ).
再根據前面的引理，不難推斷出每個環分別對稱。

證明方式與引理相類似
一個稍稍複雜點的結構,其中紅、藍色部分分別為兩組對稱的鏈結構
推廣2：對於任意一對Si, Si '  ，Si的後代節點與Si '  的前代節點相互對稱。
繼而提出:
猜測2：若問題無解，則必然存在Ai, Ai '  ，使得Ai,Ai ' 屬於同一個環。也就是，如果每一對Ai,Ai '  都不屬於同一個環，問題必定有解。下面給出簡略證明：

先提出一個跟演算法1相似的步驟：
如果選擇Si，那麼對於所有Si -> Sj，Sj都必須被選擇。
而Si '  必定不可選，這樣Si’的所有前代節點也必定不可選（將這一過程稱之為刪除）。
由推廣2可以得到，這樣的刪除不會導致矛盾。

假設選擇S3 '  
?選擇S3 ' 的後代節點, S1 '
?刪除S3
?刪除S3的前代節點S1
S1與S1 ' 是對稱的

每次找到一個未被確定的Si，使得不存在Si -> Si '  選擇Si及其後代節點而刪除Si’及Si‘的前代節點。一定可以構造出一組可行解。
因此猜測2成立。

另外，若每次盲目的去找一個未被確定的Si，時間複雜度相當高。
以自底向上的順序進行選擇、刪除，這樣還可以免去“選擇Si的後代節點”這一步。
用拓撲排序實現自底向上的順序。

一組可能的拓撲序列(自底向上）:S1 ' ,S2,S2 ' ,S3 ' ,S3,S1

演算法2的流程：
1 ．構圖 2 ．求圖的極大強連通子圖 3 ．把每個子圖收縮成單個節點，根據原圖關係構造一個有向無環圖 4 ．判斷是否有解，無解則輸出（退出） 5 ．對新圖進行拓撲排序 6 ．自底向上進行選擇、刪除 7 ．輸出

小結：
整個演算法的時間複雜度大概是O(m)，解決此問題可以說是相當有效了。
在整個演算法的構造、證明中反覆提到了一個詞：對稱。發現、利用了這個圖的特殊性質，我們才能夠很好的解決問題。
並且，由2 - SAT問題模型變換出的類似的題目都可以用上述方法解決。

全文總結：
充分挖掘圖的性質，能夠更好的解決問題。
不僅僅是對於圖論，這種思想可以在很多問題中得到很好的應用。
希望我們能掌握此種解題的思想，在熟練基礎演算法的同時深入分析、靈活運用、大膽創新，從而解決更多更新的難題。

USACO Feb12 Bronze Rope Folding 折繩子 題解

USACO 2012 February Contest, Bronze Division

Problem 1. Rope Folding

Problem 1: Rope Folding [Brian Dean, 2012] 
Farmer John has a long rope of length L (1 <= L <= 10,000) that he uses for various tasks around his farm. The rope has N knots tied into it at various distinct locations (1 <= N <= 100), including one knot at each of its two endpoints. 

FJ notices that there are certain locations at which he can fold the rope back on itself such that the knots on opposite strands all line up exactly with each-other:
  
Please help FJ count the number of folding points having this property. Folding exactly at a knot is allowed, except folding at one of the endpoints is not allowed, and extra knots on the longer side of a fold are not a problem (that is, knots only need to line up in the areas where there are two strands opposite each-other). FJ only considers making a single fold at a time; he fortunately never makes multiple folds. 

PROBLEM NAME: folding
INPUT FORMAT:
 * Line 1: Two space-separated integers, N and L.
 * Lines 2..1+N: Each line contains an integer in the range 0...L specifying the location of a single knot. Two of these lines will always be 0 and L. 

並查集練習題 島國 jx 題解

【題目描述】
很久很久很久很久很久很久以前......

有一個島國。

這個國家的領地是一塊座標從(1,1)到(K,K)的正方形（包括領海和領陸，座標(x,y)是指(x,y)這塊土地，並非一個點）

衛星資訊會告訴你這個國家的土地情況，希望你能根據給出的資訊計算出這個國家有多少個島。

衛星給出的資訊形如x1 y1 x2 y2，表示左下角座標為x1,y1,右上角座標為x2,y2的這一個矩形區域是陸地

輸入格式：

第一行一個整數n，表示衛星會傳送給你n條資訊

下面n行每行有4個整數，x1,y1,x2,y2，含義如上

輸出格式：

第一行，一個整數Sum，表示這個國家的島的數量

注，只有一個公共點的兩塊陸地不算是一塊區域，具體如樣例

OI練習題 式子 recursion

【問題描述】

動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：

一個 N 階線性遞推式是這樣的式子：

也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。

例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。

LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。

【輸入文件】

第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。

第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。

第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。

【輸出文件】

只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。

ACM/ICPC 小球鐘——時間與運動

問題描述

時間是運動的一種方式，所以常常用運動來度量時間。如圖所示的小球鍾就是一個通過不斷在軌道上移動小球來度量時間的簡單設備。

每分鐘，一個轉動臂將一個小球從小球隊列的底部擠走，將它上升到鐘的頂部並安置在一個表示分鐘， 5 分鐘和小時的軌道上。這裡可以顯示從 1:00 到 12:59 範圍內的時間，但無法表示 “a.m.” 和 “p.m.” 。若有 2 個球在分鐘軌道， 6 個球在 5 分鐘軌道及 5 個球在小時軌道上，就顯示時間 5:32 。

不幸的是，大多數市場上提供的小球鍾無法顯示日期，儘管只需要簡單地加上一些軌道就可以了。當小球通過鐘的機械裝置被移動後，它們就會改變其初始次序。仔細研究它們隨著時間的流逝發生的次序的改變，可以發現相同的次序會不斷出現。由於小球的初始次序最後遲早會被重複，所以這段時間的長短是可以被度量的，這完全取決於所提供小球的總數。

每分鐘，最近最少使用的那個小球從位於球鍾底部的小球隊列被移走，並將上升安置於顯示分鐘的軌道上，這裡可以放置 4 個小球。當第 5 個小球滾入該軌道，它們的重量使得軌道傾斜，原先在軌道上的 4 個小球按照與它們原先滾入軌道相反加入到鍾底部的小球隊列。引起傾斜的第 5 個小球滾入顯示 5 分鐘的軌道，該軌道可以放置 11 個球。當第 12 個小球滾入該軌道，它們的重量使得軌道傾斜，原先 11 個小球同樣以相反的次序加入鍾底部的小球隊列。而這第 12 個小球滾入了顯示小時的軌道。該軌道同樣可以放置 11 個球，但這裡有一個外加的固定不能被移動的小球，這樣小時的值域就變為 1 到 12 。從 5 分鐘軌道滾入的第 12 個小球將使小時軌道傾斜，這 11 個球同樣以相反的次序加入鍾底部的小球隊列，然後第 12 個小球同樣加入鍾底部的小球隊列。

輸入小球的個數，輸出該時鐘在經過多少天的運行可以回到它的初始小球序列。例如有 45 個小球的鐘經過 378 天會回到初始狀態。