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

补充：软件开发 , C++ ,