POJ - 1201 Intervals差分约束-白红宇

POJ - 1201 Intervals差分约束

阅读量：690 次

发布时间：2019-03-17

本文共 1339 字，大约阅读时间需要 4 分钟。

题目大意

给定n个区间， 求选择若干个数， 保证每个区间中选择的数不少于c

思路

根据题目的条件写出不等式

在建图时，由于用到了前缀合，我们额a,b的取值范围增加1，把取值范围变为1~50001

最后dis[50001]里面存的就是本题的答案

由于数据保证了c<=b-a+1，所以本题一定有解

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 50010, M = 150010;int e[M], ne[M], w[M], h[N], len;int n;int dis[N];bool vis[N];void add(int a, int b, int c){       e[len] = b;    w[len] = c;    ne[len] = h[a];    h[a] = len++;}void spfa(){       memset(dis, -0x3f, sizeof dis);    queue
       
         q;    q.push(0);    dis[0] = 0;    vis[0] = true;    while(q.size())    {           int x = q.front();        q.pop();        vis[x] = false;        for(int i = h[x]; ~i; i = ne[i])        {               int y = e[i];            if(dis[y] < dis[x] + w[i])            {                   dis[y] = dis[x] + w[i];                if(!vis[y])                {                       q.push(y);                    vis[y] = true;                 }            }        }    }    }int main(){       cin >> n;    memset(h, -1, sizeof h);    for(int i = 1; i<= n; i++)    {           int a, b, c;        scanf("%d%d%d", &a, &b, &c);        a ++, b++;        add(a - 1, b, c);    }        for(int i = 1; i <= 50001; i++)        add(i - 1, i, 0), add(i, i - 1, -1);        spfa();        printf("%d", dis[50001]);            return 0;}