poj 1201 TYVJ 1415 Intervals

Description：

给定n个闭区间[a，b] 和n个整数c，你需要构造一个集合Z，使得对于任何的i∈[1，n]，Z中满足x∈[a，b]的x不少于c个 求这样的整数集合Z至少包含多少个数

思路：建立差分约束系统的模型s[k]表示0~k间选取多少个整数，根据题意有s[b] -  s[a - 1] ≥ c

不过还要增加一些隐含条件   s[k] - s[k - 1] ≥ 0，s[k]  - s[k  -1] ≤ 1

因此，将输入最大的数b作为图中的节点，从每个k - 1到k连长度为0的有向边，k到k - 1连长度为 -1 的有向边。从每个到a 1 到 b 连长度为c的有向边

起点为0，终点为max（b）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

const int N = , M = 1e6 + ;

typedef pair<int,int> P;

int head[N], now;

struct edges{

    int to, next, w;

}edge[M<<];

void add(int u, int v, int w){ edge[++now] = {v, head[u], w}; head[u] = now;}

int n, d[N], s;

bool vis[N];

queue<int> q;

void spfa(){

    d[s] = ;

    q.push(s);

    vis[s] = ;

    while(!q.empty()){

        int x = q.front(); q.pop();

        vis[x] = ;

        for(int i = head[x]; i; i = edge[i].next){

            int v = edge[i].to;

            if(d[v] < d[x] + edge[i].w || (d[v] == d[x] + edge[i].w && v == x + )){

                d[v] = d[x] + edge[i].w;

                if(!vis[v]) q.push(v), vis[v] = ;

            }

        }

    }

}

int main(){

    scanf("%d", &n);

    int x, y, z;

    int mx = ;

    for(int i = ; i <= n; i++){

        scanf("%d%d%d", &x, &y, &z);

        x++, y++;  // 全都向上加1，防止数组向下溢出

        mx = max(mx, y);

        add(x - , y, z);

    }

    for(int i = ; i <= mx; i++)

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

    s = ;

    spfa();

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

    return ;

}