差分約束系統(tǒng)：如果一個(gè)系統(tǒng)由n個(gè)變量和m個(gè)約束條件組成，其中每個(gè)約束條件形如 xj - xi<= bk ( i , j ∈ [1，n]，k ∈ [1，m])，則稱其為差分約束系統(tǒng)。?
例如如下的約束條件：?
X1 - X2 <= 0 X1 - X5 <= -1?
X2 - X5 <= 1 X3 - X1 <= 5?
X4 - X1 <= 4 X4 - X3 <= -1?
X5 - X3 <= -3 X5 - X4 <= -3?
全都是兩個(gè)未知數(shù)的差小于等于某個(gè)常數(shù)（大于等于也可以，因?yàn)樽笥页艘?1就可以化成小于等于）。這樣的不等式組就稱作差分約束系統(tǒng)。?
差分約束系統(tǒng)求解過程：?
1.新建一個(gè)圖，N個(gè)變量看作N個(gè)頂點(diǎn)，M個(gè)約束條件作為M條邊。每個(gè)頂點(diǎn)Vi分別對于一個(gè)未知量，每個(gè)有向邊對應(yīng)兩個(gè)未知量的不等式。?
2.為了保證圖的連通性，在圖中新加一個(gè)節(jié)點(diǎn)Vs，圖中每個(gè)節(jié)點(diǎn)Vi都能從Vs可達(dá)，建立邊w(Vs，Vi) = 0。?
3.對于每個(gè)差分約束Xj - Xi <= Bk(這里是小于等于號)，則建立邊w(Xi，Xj) = Bk。?
4.初始化Dist[] = INF，Dist[Vs] = 0.?
5.求解以Vs為源點(diǎn)的單源最短路徑，推薦用SPFA，因?yàn)橐话憧赡艽嬖谪?fù)值。?
如果圖中存在負(fù)權(quán)回路，則該差分約束系統(tǒng)不存在可行解。?
Vs到某點(diǎn)如果不存在最短路徑，即最短路為INF，則對于該點(diǎn)表示的變量可以取任意值，都能滿足差分約束的要求，如果存在最短路徑，則得到該變量的最大值。?
上述過程最終得到的解為滿足差分約束系統(tǒng)各項(xiàng)的最大值。?
注意點(diǎn)：?
1. 如果要求最大值想辦法把每個(gè)不等式變?yōu)闃?biāo)準(zhǔn) x - y <= k 的形式,然后建立一條從 y 到 x 權(quán)值為 k 的邊，變得時(shí)候注意 x - y < k => x - y <= k-1。?
2. 如果要求最小值的話，變?yōu)?x - y >= k 的標(biāo)準(zhǔn)形式，然后建立一條從 y到 x 權(quán)值為 k 的邊，求出最長路徑即可。?
3. 如果權(quán)值為正，用Dijkstra，SPFA，BellmanFord都可以，如果為負(fù)不能用Dijkstra，并且需要判斷是否有負(fù)環(huán)，有的話就不存在。
<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<iostream></span>
<span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<algorithm></span>
<span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<cstdio></span>
<span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<cstring></span>
<span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<queue></span>
<span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#define INF 0x7fffffff</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">using</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">namespace</span> <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">std</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXN = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1100</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXM = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">30030</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> EdgeNode
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> to;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> w;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> next;
}Edges[MAXM];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Head[MAXN],Dist[MAXN],vis[MAXN],outque[MAXN],id;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> AddEdges(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> v,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> w)
{Edges[id].to = v;Edges[id].w = w;Edges[id].next = Head[u];Head[u] = id++;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> SPFA(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> s,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N)
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> ans = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(vis,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(vis));<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(outque,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(outque));<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= N; ++i)Dist[i] = INF;Dist[s] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;vis[s] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">queue</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> Q;Q.push(s);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span>( !Q.empty() ){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u = Q.front();Q.pop();vis[u] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;outque[u]++;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(outque[u] > N+<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//如果出隊(duì)次數(shù)大于N，則說明出現(xiàn)負(fù)環(huán)</span>{ans = -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">break</span>;}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = Head[u]; i != -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i = Edges[i].next){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> temp = Dist[u] + Edges[i].w;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(temp < Dist[Edges[i].to]){Dist[Edges[i].to] = temp;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>( !vis[Edges[i].to]){vis[Edges[i].to] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;Q.push(Edges[i].to);}}}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(ans == -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//出現(xiàn)負(fù)權(quán)回路，不存在可行解</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"-1\n"</span>);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Dist[N] == INF) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//可取任意值，都滿足差分約束系統(tǒng)</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"-2\n"</span>);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d\n"</span>,Dist[N]); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求使得源點(diǎn) s 到 終點(diǎn) t 的最大的值</span>
}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> main()
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N,ML,MD,u,v,w;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span>(~<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">scanf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d%d%d"</span>, &N, &ML, &MD)){<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(Head,-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(Head));id = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < ML; ++i){<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">scanf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d%d%d"</span>,&u,&v,&w);AddEdges(u,v,w);<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//建邊 u - v <= w</span>}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < MD; ++i){<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">scanf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d%d%d"</span>,&u,&v,&w);AddEdges(v,u,-w);<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//建邊 v - u <= w</span>}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//這里不加也可以</span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// for(int i = 1; i < N; ++i)</span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// AddEdges(i+1,i,0);</span>SPFA(<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>,N); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求使得源點(diǎn) s 到 終點(diǎn) t 的最大的值</span>}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;
}</code>
總結(jié)
以上是生活随笔為你收集整理的差分约束系统【模板】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
