POJ1364基本的查分约束问题

题意：

给了由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 1000000000

using 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基本的查分约束问题

最新文章

热门文章