POJ1201 Intervals【差分约束系统】

Description

You are given n closed,integer intervals [ai,bi] and n integers c1,...,cn.
Write a program that:
reads the number of intervals,their end points and integers c1,cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai,bi],for each i=1,2,n,
writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai,bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai,n.

Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

思路

发现对于整个区间的约束是可以转化成前缀和的
然后就把([a_i,b_i])这个区间的约数转化成(a_i-1和b_i)两个点，连边
然后从后向前相邻点连上权值是-1的边
从前向后连权值是0的边
然后跑一遍最长路就可以满足所有的约数条件了

注意这里的最长路，其实就是满足所有约束的最小代价

//Author: dream_maker
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a,b,c) for (int a = b; a <= c; ++a)
#define fd(a,c) for (int a = b; a >= c; --a)
#define fv(a,b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
  bool w = 1;x = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') w = 0,c = getchar();
  while (isdigit(c)) {
    x = (x<<1) + (x<<3) + c -'0';
    c = getchar();
  }
  if (!w) x = -x;
}
template <typename T>
void Write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x; 
  }
  if (x > 9) Write(x / 10);
  putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 1e5 + 10;
struct Edge {
  int v,w,nxt;
  Edge(int v = 0,int w = 0,int nxt = 0):v(v),w(w),nxt(nxt) {}
} E[N * 3];
int head[N],tot = 0;
int n,a[N],b[N],c[N],maxl = 0;
int dis[N],inq[N];
void add(int u,int v,int w) {
  E[++tot] = Edge(v,head[u]);
  head[u] = tot;
}
void spfa() {
  queue<int> q;
  q.push(0);
  fu(i,1,maxl) dis[i] = -INF_of_int;
  while (q.size()) {
    int u = q.front(); q.pop();
    inq[u] = 0;
    for (int i = head[u]; i != -1; i = E[i].nxt) {
      int v = E[i].v;
      if (dis[v] < dis[u] + E[i].w) {
        dis[v] = dis[u] + E[i].w;
        if (!inq[v]) {
          inq[v] = 1;
          q.push(v);
        }
      }
    }
  }
}
int main() {
  Read(n);
  memset(head,-1,sizeof(head));
  fu(i,n) {
    Read(a[i]); ++a[i];
    Read(b[i]); ++b[i];
    Read(c[i]);
    maxl = max(maxl,max(a[i],b[i]));
    add(a[i] - 1,b[i],c[i]);
  }
  fu(i,maxl) add(i - 1,i,0);
  fu(i,maxl) add(i,i - 1,-1);
  spfa();
  Write(dis[maxl]);
  return 0;
}