题目链接：传送门

Intervals

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4314    Accepted Submission(s): 1631 Problem 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 endpoints 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 <= 50 000) - 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 <= 50 000 and 1 <= ci <= bi - ai + 1. Process to the end of file.   Output The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.   Sample Input 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1   Sample Output 6

题目大意：给定n个区间[ai,bi],这n个区间中对应的每个区间至少要有ci个数，求满足这些条件最少需要的数

解题思路：差分约束，写出约束方程，将每个数看成一个点，建图,求最长路

对于第i个区间:D[bi]-D[ai-1]>=ci

隐藏的条件:D[i]-D[i-1]>=0，D[i]-D[i-1]<=1(D[i-1]>=D[i]-1)

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<stack> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int>PA; const int N = 50005; const int M = 1000; const int INF = 0x3fffffff; const int mod = 1e9+7; struct Edge{ int node,len; Edge*next; }m_edge[N*10]; Edge*head[N]; int Ecnt,vis[N],dist[N]; void init() { Ecnt = 0; fill( head , head+N , (Edge*)0 ); } void mkEdge( int a , int b , int c ) { m_edge[Ecnt].node = b; m_edge[Ecnt].len = c; m_edge[Ecnt].next = head[a]; head[a] = m_edge+Ecnt++; } void spfa( int n ) { fill( vis , vis+N , 0 ); fill( dist , dist+N , -INF ); queue<int>point; vis[n] = 1; dist[n] = 0; point.push(n); while( !point.empty() ){ int s = point.front(); point.pop(); vis[s] = 0; for( Edge*p = head[s] ; p ; p = p->next ){ int t = p->node; if( dist[t] < dist[s]+p->len ){ dist[t] = dist[s]+p->len; if( !vis[t] ){ vis[t] = 1; point.push(t); } } } } } int main() { int n; while( cin >> n ){ init(); int a,b,c,mx = 0; for( int i = 0 ; i < n ; ++i ){ cin >> a >> b >> c; mx = max(mx,b); mkEdge( a-1 , b , c ); } for( int i = 1 ; i <= mx ; ++i ){ mkEdge( i-1 , i , 0 ); mkEdge( i , i-1 , -1 ); } spfa(0); cout << dist[mx] << endl; } return 0; }