題意：
? ? ? 給了由n個數組成的一個數列，然后給你各種區間的和是大于ci還是小于ci啥的，最后問你是否沖突。


思路：
? ? ? 差分約束水題，不過wa了兩次，原因處理區間問題的細節馬虎了，說下建圖吧，這個題目給的是大于或者小于，不是大于等于啥的，其實這個好辦，直接進行相應的+-1就能添加等于號了，然后進行關系轉換
假如輸入的是 a b str c
b = a + b + 1 //一開始忘記了區間的這個處理方法忘記+1
那么if(str[0] == g)
b - a > c
b - a >= c + 1
直接建邊 add(a ,b ,c + 1);
else
b - a < c
b - a <= c - 1
a - b >= -(c-1)
add(b ,a ,-(c-1));

上面的建圖是跑最上路的，也可以不這么建圖，就是全部都反過來，然后跑最短路，還有就是差分約束很多題目需要我們補充連通性，就是虛擬出來一個0，連接所有點，距離是0，這樣是為了防止真個圖不連通，當然，如果你想mark然后for去多次最短路也行，這個題目還有一個地方，就是b=a+b+1中的+1可能會導致n+1，所以記得n++后在跑最短路，別的沒啥題目不難，不涉及到隱含條件。

#include<queue> #include<stdio.h> #include<string.h>#define N_node 100 + 10 #define N_edge 100 + 20 #define INF 1000000000using namespace std;typedef struct {int to ,next ,cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node] ,mark[N_node] ,mkc[N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }bool SPFA(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = -INF ,mark[i] = mkc[i] = 0;queue<int>q;q.push(s);s_x[s] = 0;mark[s] = mkc[s] = 1;while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] < s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;if(++mkc[xin] > n) return 0;q.push(xin);}}}}return 1; }int main () {int i ,n ,m ,a ,b ,c;char str[10];while(~scanf("%d" ,&n) && n){scanf("%d" ,&m);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d %s %d" ,&a ,&b ,str ,&c);b = a + b + 1;if(str[0] == 'g') add(a ,b ,c + 1);else add(b ,a ,-(c - 1));}n++;for(i = 1 ;i <= n ;i ++)add(0 ,i ,0);if(!SPFA(0 ,n)) printf("successful conspiracy\n");else printf("lamentable kingdom\n");}return 0; }

總結

以上是生活随笔為你收集整理的POJ1364基本的查分约束问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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