POJ1201 Intervals （进阶指南， 差分约束，spfa）

算法竞赛进阶指南，394页，差分约束系统， spfa
题目意思：
有n段区间, 起点和终点分别是 a[i], b[i]; 要求在没段区间选 c[i]个数。
求：最少选几个数满足条件;
本题要点：
1、 s[k]表示 从 0 ~ k 之间最少选出多少个数；
那么从 a[i] 和 b[i]之间选c[i] 个数，满足条件 s[b[i]] - s[a[i] - 1] >= c[i],
这个等式符合差分约束系统;
同时，从 0 ~ k 之间选 比从 0 ~ k -1 之间选的数要多， 满足 s[k] - s[k - 1] >= 0;
每个数只选一次， s[k] - s[k - 1] <= 1, 变形为 ：s[k - 1] - s[k] >= -1;

2、上面的3条式子，s[b[i]] - s[a[i] - 1] >= c[i], 表示 从 a[i] - 1 到 b[i] 连长度为c[i] 的有向边；
s[k] - s[k - 1] >= 0, 表示 从 k - 1 到 k 连长度为 0 的有向边；
s[k - 1] - s[k] >= -1, 表示 从 k 到 k - 1连长度为 -1 的有向边；
起点为 -1 ，另 s[-1] == 0, 求单源最长路径。 s[maxNum] 就是答案， maxNum 是出现过的最大的下标 b[i]

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int MaxN = 50010;
int n;
int a[MaxN], b[MaxN], c[MaxN];
int head[MaxN], ver[MaxN * 4], edge[MaxN * 4], Next[MaxN * 4], d[MaxN];
bool vis[MaxN];
int tot, maxNum = -1;void add(int x, int y, int z)
{
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}void spfa()
{
    memset(d, 0x80, sizeof(d));memset(vis, false, sizeof(vis));d[MaxN - 1] = 0, vis[MaxN - 1] = true;queue<int> q;q.push(MaxN - 1);while(q.size()){
    int x = q.front(); q.pop();vis[x] = false;for(int i = head[x]; i; i = Next[i]){
    int y = ver[i], z = edge[i];if(d[y] < d[x] + z){
    d[y] = d[x] + z;if(!vis[y]){
    q.push(y);vis[y] = true;}}}}
}int main()
{
    int st = MaxN - 1;int x, y, z;scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%d%d%d", &a[i], &b[i], &c[i]);maxNum = max(maxNum, b[i]);x = a[i] - 1;y = b[i], z = c[i];if(-1 == x){
    x = st;	//原本是以 下标为-1 的点为原点的，用 st 来代替 -1}add(x, y, z);}add(st, 0, 0);add(0, st, -1);for(int i = 1; i <= maxNum; ++i){
    add(i - 1, i, 0);add(i, i - 1, -1);}spfa();printf("%d\n", d[maxNum]);return 0;
}/* 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1 *//* 6 */