題目描述有點復雜，前面講了一大堆廢話。

題目大意：對一個含n個整數的序列進行一些約束：

1、整數序列中連續的一段的和大于某個整數；

2、整數序列中連續的一段的和小于某個整數。

問滿足以上約束的整數序列是否存在。

分析：首先利用前綴和進行轉換，然后將>化為>=,將<化為<=,然后就基本是裸的差分約束系統了。

需要注意的是，建立的約束圖可能并不是無向連通的，所以需要另外加一個結點作為源點，由于加了一個點，所以判斷是否有負環時要注意，條件是某個點進隊次數大于n+1

View Code #include <stdio.h> #include <string.h> #include <queue> using namespace std; #define N 110 #define M 210 #define INF 0x3fffffff int n,m; int d[N]; int inq[N],cnt[N]; int first[N],v[M],next[M],w[M]; int e; void init() {e=0;memset(first,-1,sizeof(first)); } void insert(int a,int b,int c) {v[e]=b;w[e]=c;next[e]=first[a];first[a]=e++; } void spfa() {queue<int> q;int a,b;bool loop=false;memset(inq,0,sizeof(int)*(n+5));memset(cnt,0,sizeof(int)*(n+5));for(int i=0;i<=n;i++) d[i]=INF;d[n+1]=0;inq[n+1]=1;q.push(n+1);cnt[n+1]++;while(!q.empty()){a=q.front(),q.pop();if(cnt[a]>n+1) { loop=true; break; }inq[a]=0;for(int i=first[a];i!=-1;i=next[i]){b=v[i];if(d[b]>d[a]+w[i]){d[b]=d[a]+w[i];if(inq[b]==0) inq[b]=1,q.push(b),cnt[b]++;}}}if(loop) puts("successful conspiracy");else puts("lamentable kingdom"); } int main() {int i;int a,b,c;char s[5];while(scanf("%d",&n),n){init();scanf("%d",&m);for(i=0;i<m;i++){scanf("%d%d%s%d",&a,&b,s,&c);if(s[0]=='g'){insert(a+b,a-1,-c-1);}else{insert(a-1,a+b,c-1);}}for(i=0;i<=n;i++) insert(n+1,i,0);spfa();}return 0; }

轉載于:https://www.cnblogs.com/algorithms/archive/2012/07/24/2606894.html

總結

以上是生活随笔為你收集整理的POJ 1364 King （差分约束系统）的全部內容，希望文章能夠幫你解決所遇到的問題。

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