查分約束系統(tǒng)-王毅峰課件

查分約束系統(tǒng)T1-工程規(guī)劃-work【問題描述】

造一幢大樓是一項艱巨的工程，它是由n個子任務(wù)構(gòu)成的，給它們分別編號1，2，…，n(5≤n≤1000)。由于對一些任務(wù)的起始條件有著嚴格的限制，所以每個任務(wù)的起始時間T1，T2，…，Tn并不是很容易確定的(但這些起始時間都是非負整數(shù)，因為它們必須在整個工程開始后啟動)。例如：挖掘完成后，緊接著就要打地基；但是混凝土澆筑完成后，卻要等待一段時間再去掉模板。這種要求就可以用M(5≤m≤5000)個不等式表示，不等式形如Ti一Tj≤b代表i和j的起始時間必須滿足的條件。每個不等式的右邊都是一個常數(shù)b，這些常數(shù)可能不相同，但是它們都在區(qū)間(-l00，100)內(nèi)。你的任務(wù)就是寫一個程序，給定像上面那樣的不等式，找出一種可能的起始時間序列T1，T2，…，Tn，或者判斷問題無解。對于有解的情況，要使最早進行的那個任務(wù)和整個工程的起始時間相同，也就是說，T1，T2，…，Tn中至少有一個為0。題目大意我們有n個任務(wù)，都可以在瞬間做完我們做這n個任務(wù)的時刻分別為T1,T2,T3,T4…我們對這n個任務(wù)的時刻有m組要求我們假設(shè)每組要求的格式為Ti,Tj,b我們的要求是Ti-Tj<=b樣例255

12-3

15-1

25-1

51-5

414NOSOLUTION不等式x-y<=1x-y<=1x<=y+1y-x>=-1注意，后一個在數(shù)學(xué)上貌似是不對的讓我們推倒一下Ti-Tj<=bTi<=Tj+b觀察一下有沒有想到什么？dist[i]<=dist[j]+v[j][i]這是一個目標(biāo)狀態(tài)如何達到目標(biāo)狀態(tài)呢？如果dist[i]>dist[j]+v[j][i]那么dist[i]=dist[j]+v[j][i]最終就可以達到前面的狀態(tài)。查分約束系統(tǒng)的思想既然我們可以把一個形如Ti-Tj<=b的不等式轉(zhuǎn)化為Ti<=Tj+b的目標(biāo)狀態(tài)那么我們就可以建圖，由點j向點i連一條長度為b的單向邊然后以某一個點為起點，定義它的值位0。求出最短路，即為答案。當(dāng)然此題需要處理一下使他們都大于零練習(xí)題P1227關(guān)系運算圖

描述Description

給出一有向圖，圖中每條邊都被標(biāo)上了關(guān)系運算符‘<’,‘>’,‘=’。現(xiàn)在要給圖中每個頂點標(biāo)上一個大于等于0,小于等于k的某個整數(shù)使所有邊上的符號得到滿足。若存在這樣的k，則求最小的k，若任何k都無法滿足則輸出NO。

例如下表中最小的k為2。

結(jié)點1>結(jié)點2

結(jié)點2>結(jié)點3

結(jié)點2>結(jié)點4

結(jié)點3=結(jié)點4

如果存在這樣的k，輸出最小的k值；否則輸出‘NO’。對于a<b，他和之前我們的Ti-Tj<=b的區(qū)別有兩個，一個是常數(shù)項，另一個是不能相等。因為是整數(shù)，所以可以進行轉(zhuǎn)化a+1<=b然后再推倒一下建圖就可以了然后建立一個源點，從源向其他所有點連一條權(quán)值為0的單向邊以源點為出發(fā)點，進行一遍最短路什么時候無解？存在負權(quán)回路的就是無解。還有一道作業(yè)題P1624layoutFj的牛每天要排隊去吃飯。

現(xiàn)在有N(2<=N<=1000)只牛要排隊吃飯，這個隊伍我們可以認為是數(shù)軸，數(shù)軸上每個整數(shù)點我們認為可以站牛，并且可以站無數(shù)頭牛。

牛們對排隊的順序有要求，如果有兩頭牛的關(guān)系很好，他們之間的距離不能超過一定的距離，如果有兩頭牛關(guān)系不好，他們的距離不能低于一定的距離。

在滿足這個所有條件的基礎(chǔ)上，