POJ1201基础差分约束

题意：

有一条直线，直线上做多有50000个点，然后给你组关系 a b c表明a-b之间最少有c个点，问直线上最少多少个点。

思路：

a-b最少有c个点可以想象a到b+1的距离是大于等于c的，还有一个隐含条件就是

0<=S[i] - S[i-1]<=1,差分约束的题目记住找隐含条件很重要，这样也就是一共三个条件，建边求最上路，记住查分约束求短要用最长路，求最长要用最短路，最长路的建边是

a ,b c

S[i-1] ,S[i] 0

S[i] ,S[i-1] -1

#include<queue>

#include<stdio.h>

#include<string.h>

#define N_node 50000 + 100

#define N_edge 150000 + 10000

#define INF 1000000000

using namespace std;

typedef struct

{

    int to ,cost ,next;

}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);

    mark[s] = mkc[s] = 1;

    s_x[s] = 0;

    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 t ,i ,a ,b ,c ,m ,min ,max;

    while(~scanf("%d" ,&m))

    {

        memset(list ,0 ,sizeof(list));

        tot = 1;

        min = INF ,max = 0;

        for(i = 1 ;i <= m ;i ++)

        {

            scanf("%d %d %d" ,&a ,&b ,&c);

            add(a ,++b ,c);

            if(min > a) min = a;

            if(max < b) max = b;

        }

        for(i = min + 1 ;i <= max ;i ++)

        {

            add(i-1 ,i ,0);

            add(i ,i-1 ,-1);

        }

        SPFA(min ,max);

        printf("%d\n" ,s_x[max]);

    }

    return 0;

}

巴特西

POJ1201基础差分约束

最新文章

热门文章