Yeefan's Blog: 2012

2012年3月16日星期五

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

/*

*Problem: NOIP模擬題 收費站

*Author: YeefanZhu

*Website: www.yeefanblog.tk

*GTalk: zyfworks@gmail.com

*/

#include <cstdio>

#include <vector>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN=10001;

const int INF=1100000000;

int Cost[MAXN],BS[MAXN];

int N,M,S,B,E;

vector<int> Map[MAXN];

vector<int>Val[MAXN];



inline void init()

{

    scanf("%d %d %d %d %d\n",&N,&M,&B,&E,&S);

    for(int i=1;i<=N;i++)

    {

        scanf("%d\n",&Cost[i]);

        BS[i]=Cost[i];

    }

    sort(BS+1,BS+N+1);

    int a,b,v;

    for(int i=1;i<=M;i++)

    {

        scanf("%d %d %d\n",&a,&b,&v);

        Map[a].push_back(b);

        Map[b].push_back(a);

        Val[a].push_back(v);

        Val[b].push_back(v);

    }

}



priority_queue<pair<int,int> > PQ;

int Used[MAXN];

int Dist[MAXN];



inline bool SP(int x)

045

{

    if(Cost[B]>x) return false;

    for(int i=1;i<=N;i++) {Used[i]=0,Dist[i]=INF;}

    Dist[B]=0;

    PQ.push(make_pair(0,B));

    int u,v,cost;

    while(!PQ.empty())

    {

        u=PQ.top().second;

        PQ.pop();

        if(!Used[u])

        {

            Used[u]=1;

            for(unsigned int i=0;i<Map[u].size();i++)

            {

                v=Map[u][i];

                cost=Val[u][i];

                if(Cost[v]>x) continue;

                if(!Used[v]&&Dist[v]-Dist[u]>cost)

                {

                    Dist[v]=Dist[u]+cost;

                    PQ.push(make_pair(-Dist[v],v));

                }

            }

        }

    }

    if(Dist[E]>S) return false;

    return true;

}



inline void solve()

{

    int L=1,R=N;

    int Mid;

    if(!SP(BS[N])) {printf("-1\n");return;}

    int Ans;

    bool flag;

    while(L<=R)

    {

        Mid=(L+R)>>1;

        flag=SP(BS[Mid]);

        if(flag)

        {

            Ans=BS[Mid];

            R=Mid-1;

        }

        else L=Mid+1;

    }

    printf("%d\n",Ans);

}



int main()

{

    freopen("cost.in","r",stdin);

    freopen("cost.out","w",stdout);

    init();

    solve();

    return 0;

}

2012年3月6日星期二

【轉載】淺談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問題模型變換出的類似的題目都可以用上述方法解決。

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

2012年3月3日星期六

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.

兩站間距離 - X	票價
0<X<=L₁	C₁
L₁<X<=L₂	C₂
L₂<X<=L₃	C₃

申請SAE

2012年3月16日 星期五

2012年3月6日 星期二

2012年3月3日 星期六

USACO 2012 February Contest, Bronze Division

Problem 1. Rope Folding

2012年2月28日 星期二

2012年2月27日 星期一

2012年2月20日 星期一

2012年2月18日 星期六

2012年2月16日 星期四

2012年2月12日 星期日

2012年2月11日 星期六

2012年2月10日 星期五

2012年3月16日星期五

2012年3月6日星期二

2012年3月3日星期六

2012年2月28日星期二

2012年2月27日星期一

2012年2月20日星期一

2012年2月18日星期六

2012年2月16日星期四

2012年2月12日星期日

2012年2月11日星期六

2012年2月10日星期五