| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 28676 | Accepted: 11065 |
Description
Input
Output
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6
Source
题解：
一道典型的差分约束问题。（没学过差分约束的同学可以看这篇讲解：传送门）
我们设d[i]表示前i个数中被选的数的个数，则区间限制变成了d[ri]-d[li-1]>=ci. 建图之后设跑最长路即可。
需要注意的是题目中的隐含条件：d[i]>=d[i-1],d[i-1]>=d[i]-1
又由于[0,x]这样的区间会出现d[-1]这样的情况，所以我们稍作改变，让d[i]表示前i-1个数中被选数的个数，起点为d[0]=0.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<bitset> 7 #define LL long long 8 #define RI register int 9 using namespace std; 10 const int INF = 0x7ffffff ; 11 const int N = 50000 + 10 ; 12 13 inline int read() { 14 int k = 0 , f = 1 ; char c = getchar() ; 15 for( ; !isdigit(c) ; c = getchar()) 16 if(c == ‘-‘) f = -1 ; 17 for( ; isdigit(c) ; c = getchar()) 18 k = k*10 + c-‘0‘ ; 19 return k*f ; 20 } 21 struct Edge { 22 int to, next, val ; 23 }e[N<<2] ; 24 int n ; int head[N], dis[N], num[N] ; 25 inline void add_edge(int x,int y,int z) { 26 static int cnt = 0 ; 27 e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt, e[cnt].val = z ; 28 } 29 30 inline bool spfa() { 31 for(int i=0;i<N;i++) dis[i] = INF ; 32 queue<int>q ; q.push(0), dis[0] = 0 ; bitset<N>inq ; inq[0] = 1 ; 33 while(!q.empty()) { 34 int x = q.front() ; q.pop() ; 35 if(num[x] > n) return 0 ; 36 for(int i=head[x];i;i=e[i].next) { 37 int y = e[i].to ; 38 if(dis[y] > dis[x]+e[i].val) { 39 dis[y] = dis[x]+e[i].val ; 40 if(!inq[y]) { 41 q.push(y) ; inq[y] = 1 ; num[y]++ ; 42 } 43 } 44 } 45 inq[x] = 0 ; 46 } 47 return 1 ; 48 } 49 50 int main() { 51 n = read() ; int maxx = 0, minn = INF ; 52 for(int i=1;i<=n;i++) { 53 int x = read(), y = read(), z = read() ; 54 maxx = max(maxx,y+1), minn = min(minn,x) ; 55 add_edge(x,y+1,-z) ; 56 } 57 add_edge(0,minn,0) ; 58 for(int i=minn;i<=maxx;i++) add_edge(i,i+1,0), add_edge(i+1,i,1) ; 59 if(!spfa()) { 60 printf("No solution!") ; return 0 ; 61 } 62 printf("%d",-dis[maxx]) ; 63 return 0 ; 64 }
原文：https://www.cnblogs.com/zub23333/p/8830281.html