poj1364-還是建模

根據題意此題是< 和> 的關系，但是若是想用差分約束，必須是>= 或者<=。
題目給出條件是整數，這就是提示，所以如果>c那麼就>=c-1,同理<也是。
知道了這，直接判有沒有負環就行了，不要忘了多加一個源點，保持圖的聯通性。。。。
 
 
代碼：
 
[cpp]
#include <stdio.h> 
 
#define maxN 205//最大頂點數，這裡是s[i] 
#define inf 0x7fffffff 
 
struct Edge  
{ 
    int v, w, next; 
}edge[maxN * 30];//邊 
 
int edgeNum;//邊總數 
int dis[maxN];//最長路徑中的dis[i]代表遠點到i的最長距離 
bool vis[maxN];//標示i是否進入隊列 
int preEdge[maxN];//同一個起點的上一條邊 
int cnt[maxN];//入隊列的次數 
int queue[maxN * 30];//模擬隊列 
int n,m;//輸入的n 
char ch[10]; 
 
void addEdge(int u, int v, int w)//添加新邊 
{ 
    edge[edgeNum].v = v; 
    edge[edgeNum].w = w; 
    edge[edgeNum].next = preEdge[u];//以u為起點的上一條邊 
    preEdge[u] = edgeNum ++; 
} 
 
int spfa()//spfa算法實現 
{ 
    int head = 0, tail = 1; 
 
    for (int i = 0; i <= n; ++ i) 
    { 
        dis[i] = inf; 
        vis[i] = false; 
        cnt[i] = 0; 
    } 
    queue[ head] = n + 2; 
    dis[n + 2] = 0; 
    ++ cnt[n + 2]; 
    while (head < tail) 
    { 
        int u = queue[head]; 
        int p = preEdge[u]; 
        vis[u] = true; 
        while (p != -1) 
        { 
            int v = edge[p].v, w = edge[p].w; 
            if (dis[v] > dis[u] + w) 
            { 
                dis[v] = dis[u] + w; 
                if (!vis[v]) 
                { 
                    vis[v] = true; 
                    queue[tail] = v; 
                    tail ++; 
                    if(++cnt[v] > n ) 
                    { 
                        return 1; 
                    } 
 
                } 
 
 
            } 
            p = edge[p].next; 
        } 
        head ++; 
        vis[u] = false; 
    } 
    return 0; 
} 
 
void buildGraph()//建圖這也是本題目的關鍵，建模。。。。 
{ 
    edgeNum = 0; 
    for (int i = 0; i <= n + 2; ++ i) 
    { 
        preEdge[i] = -1; 
    } 
    scanf("%d", &m); 
     
    for (int i = 0; i < m; ++ i) 
    { 
        int u, v, w; 
        scanf("%d %d %s %d", &u, &v, ch, &w); 
        if (ch[0] == 'g') 
        { 
            addEdge(u + v, u - 1, - w - 1); 
        } 
        else 
            addEdge(u - 1, u + v, - 1 + w); 
    } 
    for (int i = 1; i <= n; ++ i) 
    { 
        addEdge(n + 2, i, 0); 
    } 
     
} 
 
int main()//主函數 
{ 
    while (scanf("%d", &n) != EOF && n) 
    { 
        buildGraph(); 
        if (spfa()) 
        { 
            printf("successful conspiracy\n"); 
        } 
        else 
            printf("lamentable kingdom\n"); 
    } 
    return 0; 
} 

作者：zhang20072844