題目：http://poj.org/problem?id=1364

題意：就是簡單的差分約束模型。

分析：首先我們必須知道，如果圖中存在負權回路，那么差分約束沒有可行解。而存在負權回路的條件是：圖中某條邊的松

弛操作的次數超過n次。對于Bellman_Ford，我們很容易解。如下：

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 105; const int INF = 1<<29;struct Edge {int s,t;int w; };Edge edge[N*N];int dist[N]; int cnt,n,m;void add(int u,int v,int w) {edge[cnt].s = u;edge[cnt].t = v;edge[cnt].w = w;cnt++; }void Relax(int s,int t,int w) {if(dist[t] > dist[s] + w)dist[t] = dist[s] + w; }bool Bellman_Ford(int s) {for(int i=0; i<n; i++)dist[i] = INF;dist[s] = 0;for(int i=0; i<n; i++)for(int j=0; j<cnt; j++)Relax(edge[j].s,edge[j].t,edge[j].w);for(int i=0; i<cnt; i++)if(dist[edge[i].t] > dist[edge[i].s] + edge[i].w)return true;return false; }int main() {char str[5];while(cin>>n){if(n == 0) break;cin>>m;cnt = 0;while(m--){int a,b,c;cin>>a>>b>>str>>c;if(str[0]=='l')add(a-1,a+b,c-1);elseadd(a+b,a-1,-c-1);}if(Bellman_Ford(0)) cout<<"successful conspiracy"<<endl;else cout<<"lamentable kingdom"<<endl;}return 0; }
Bellman_Ford算法的時間復雜度為O(VE)，算法簡單，適用范圍又廣，雖然復雜度稍高，仍不失為一個很實用的算法。

對于判斷負權回路問題，我們還是用Spfa算法最好，時間復雜度比較低。實際上Spfa跟Bellman_Ford算法差不多，Spfa

是Bellman_Ford算法的一種隊列實現，大大減少了不必要的冗余計算。

下面是Spfa判斷負權回路的方法：

#include <iostream> #include <string.h> #include <stdio.h> #include <queue>using namespace std; const int N = 105; const int INF = 1<<29;struct Edge {int to;int w;int next; };Edge edge[N*N];bool vis[N]; int head[N],time[N],dist[N];int n,m,cnt; queue<int> Q;void add(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++; }void Init() {cnt = 0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(time,0,sizeof(time)); }bool Spfa(int s) {for(int i=0; i<=n+1; i++)dist[i] = -INF;dist[s] = 0;time[s] = 1;vis[s] = 1;while(!Q.empty()) Q.pop();Q.push(s);while(!Q.empty()){int u =Q.front();vis[u] = 0;Q.pop();for(int i=head[u]; ~i; i=edge[i].next){int v = edge[i].to;int w = edge[i].w;if(dist[v] < dist[u] + w){dist[v] = dist[u] + w;if(!vis[v]){vis[v] = 1;Q.push(v);time[v]++;if(time[v] > n)return false;}}}}return true; }int main() {char str[5];while(cin>>n){Init();if(n == 0) break;cin>>m;for(int i=0; i<n+1; i++)add(0,i,0);while(m--){int a,b,c;cin>>a>>b>>str>>c;if(str[0] == 'g')add(a + b + 1,a,c + 1);elseadd(a,a + b + 1,1 - c);}int s = 0;if(Spfa(s)) cout<<"lamentable kingdom"<<endl;else cout<<"successful conspiracy"<<endl;}return 0; }

當然，對于Spfa判負環，實際上還有優化：就是把判斷單個點的入隊次數大于n改為：如果總的點入隊次數大于所有點兩倍

時有負環，或者單個點的入隊次數大于sqrt(點數)有負環。這樣時間復雜度就降了很多了。

經典題目：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3666

分析：本題要先取對數，然后轉化為差分約束模型，再判斷有沒有解就可以了。注意這里時間限制緊，判負環要優化。

題目：http://poj.org/problem?id=3259

分析：典型的差分約束題目，直接判斷負環就行，這里數據不大，可以直接就用單個點入隊次數是否超過n判斷就可以了。

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1384

題意：在每個區間上至少選擇個元素，構成一個集合S，使得集合S中的元素最少。

分析：設表示在區間上選擇的元素的個數。那么有：，并且很明顯還有：

，然后我們根據這兩個不等式建圖，然后就轉化為最長路徑問題。

#include <iostream> #include <string.h> #include <stdio.h> #include <queue>using namespace std; const int N = 50005; const int INF = 1<<30;struct Edge {int to;int w;int next; };Edge edge[4*N];bool vis[N]; int head[N],dist[N]; int cnt,s,t;queue<int> Q;void Init() {cnt = 0;memset(vis,0,sizeof(vis));memset(head,-1,sizeof(head)); }void add(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++; }void Spfa(int s) {for(int i=0; i<N; i++)dist[i] = -INF;dist[s] = 0;while(!Q.empty()) Q.pop();Q.push(s);vis[s] = 1;while(!Q.empty()){int u = Q.front();vis[u] = 0;Q.pop();for(int i=head[u]; ~i; i=edge[i].next){int v = edge[i].to;int w = edge[i].w;if(dist[v] < dist[u] + w){dist[v] = dist[u] + w;if(!vis[v]){vis[v] = 1;Q.push(v);}}}} }int main() {int n;while(~scanf("%d",&n)){Init();s = INF;t = -1;while(n--){int u,v,w;scanf("%d%d%d",&u,&v,&w);if(u < s) s = u;if(v + 1 > t) t = v + 1;add(u,v+1,w);}for(int i=s; i<=t; i++){add(i,i-1,-1);add(i-1,i,0);}Spfa(s);printf("%d\n",dist[t]);}return 0; }

總結

以上是生活随笔為你收集整理的差分约束系统之Bellman_Ford与Spfa判断负权回路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。