題意
有n個數的序列, 下標為[1.. N ], 限制條件為: 下標從 si 到 si+ni 的項求和 < 或 > ki. 一共有m個限制條件. 問是否存在滿足條件的序列.
思路
轉化為差分約束, 就是
即 Si 為第 i 項的前綴和, 特別的 So 為0. 轉化不等式(連續子段和變為前綴和之差 > < 變為 >= <= ),求最短路, 判斷有沒有負權回路.
注意
由于并不知道圖是否連通
(不像是之前的那道Candies圖一定是聯通的,選擇班長所代表的點即可)
所以正常情況下是要另設一個"超級源點", 連接圖上的每個點, 從這個點出發就一定可以遍歷到每一個點.
"超級源點"到每個點的邊權是任意的,而它自己的點權自然是0.
這樣的話,就求出了一組滿足每對點的差盡可能大, 并且其中的d[0] = 0的解.
1. 將所有點(包括"超級源點")同時平移, 均為滿足所有約束的可行解(包括新加入的邊權們)
2. 將原圖中的所有點同時平移, 得到所有滿足原有約束的可行解. 但是仍有d[0] = 0的此時, 與超級源點的這些約束有可能不滿足. 但是顯然這是無所謂的.
3. 由此可知, 超級源點的作用就在于確保圖的連通性,使得每一個點都有一個"距離". 而"超級源點"帶來的額外約束一是d[0] = 0, 二是新加的邊權. 二者影響的都是d[1]到d[n]的浮動情況(d[0]是參考零點, 額外的邊權約束則是起到了限制d[1]到d[n]與d[0]的距離的作用,一堆不等式同樣是選擇了限制最嚴的那些并且距離盡可能大....沒有實際意義...)
總之參考零點就是這樣~
但是用SPFA只是判斷負環的話,只需要初始時將所有點入隊(而非只將源點入隊), 然后判斷每個點的入隊次數. 如果超過點的總數, 說明存在負環.否則不存在.
數值上是從INF開始減, 有負環的話就會一直減... 沒有的話就會正常退出, 當然這個時候d[ ] 值會很大..
SFPA + stack
?
//132K 16MS
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int MAXN = 105;
const int MAXE = 105;
const int INF = 0x3f3f3f3f;
struct pool
{int v,pre,w;
} p[MAXE];
int num,head[MAXN],d[MAXN],n,m,enq[MAXN];
bool inq[MAXN];
stack<int> s;
void clear()
{while(!s.empty()) s.pop();memset(head,0,sizeof(head));memset(d,0x3f,sizeof(d));memset(inq,false,sizeof(inq));memset(enq,0,sizeof(enq));num = 0;
}bool SPFA()
{for(int i=0;i<=n;i++){s.push(i);inq[i] = true;enq[i]++;}d[0] = 0;while(!s.empty()){int u = s.top();s.pop();inq[u] = false;for(int tmp=head[u],v;v=p[tmp].v,tmp;tmp=p[tmp].pre){int w = p[tmp].w;if(d[v]>d[u]+w){d[v] = d[u] + w;if(!inq[v]){inq[v] = true;enq[v]++;if(enq[v]>n+1) return false;s.push(v);}}}}return true;
}void add(int u, int v ,int w)
{p[++num].v = v;p[num].w = w;p[num].pre = head[u];head[u] = num;
}int main()
{while(scanf("%d",&n)==1 && n){clear();scanf("%d",&m);while(m--){int si,ni,ki;char o,p;scanf("%d %d %c%c %d",&si,&ni,&o,&p,&ki);if(o=='g') add(si+ni,si-1,-ki-1);else add(si-1,si+ni,ki-1);}printf(SPFA()?"lamentable kingdom\n":"successful conspiracy\n");}
}
?
?
用Bellman-Ford也可以.這個時候就要用到超級源點啦
?
//120K 0MS
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 105;
const int MAXE = 210;
const int INF = 0x3f3f3f3f;
int s[MAXE],e[MAXE],w[MAXE];
int num,d[MAXN],n,m;void clear()
{memset(d,0x3f,sizeof(d));num = 0;
}bool Bellman_Ford()
{d[n+1] = 0;for(int i=0;i<=n+1;i++){for(int j=1;j<=num;j++){if(d[e[j]]>d[s[j]]+w[j]) d[e[j]] = d[s[j]] + w[j];}}for(int j=1;j<=num;j++){if(d[e[j]]>d[s[j]]+w[j]) return false;}return true;
}void add(int u, int v ,int c)
{s[++num] = u;e[num] = v;w[num] = c;
}int main()
{while(scanf("%d",&n)==1 && n){clear();scanf("%d",&m);while(m--){int si,ni,ki;char o,p;scanf("%d %d %c%c %d",&si,&ni,&o,&p,&ki);if(o=='g') add(si+ni,si-1,-ki-1);else add(si-1,si+ni,ki-1);}for(int i=0;i<=n;i++){add(n+1,i,0);}printf(Bellman_Ford()?"lamentable kingdom\n":"successful conspiracy\n");}
}
?
?
?
)
