【题解】 POJ 1201 Intervals（差分约束）

懒得复制，戳我戳我

Solution:

• 这道题就是一个板子题
• 抽象成第(a)至第(b)间选择数的个数为(c)，我们就可以用前缀和来表示，这样就可以得到不等式(s[b]-s[a-1]>=c)，然后就可以差分约束了
• 这一个约束条件不够，因为每个数只能选择一次，所以补上(s[i+1]-s[i]>=0)和(s[i+1]-s[i]<=1)，注意存在(0)与(-1)的连边，我们可以吧(-1)拿出来用大于(50000)的数字来表示
• 然后求单元最大路径，随后的(s[50000])就是所求解

---

Code:

//It is coded by Ning_Mew on 3.27
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=5e5+10;

int n;
int head[maxn],cnt=-1,dist[maxn];
struct Edge{
  int nxt,to,dis;
}edge[maxn*5];

void add(int from,int to,int dis){
  edge[++cnt].nxt=head[from];
  edge[cnt].to=to;
  edge[cnt].dis=dis;
  head[from]=cnt;
}
void SPFA(){
  queue<int>Q;while(!Q.empty())Q.pop();
  bool vis[maxn]; memset(vis,false,sizeof(vis));
  Q.push(50001);vis[50001]=true;
  while(!Q.empty()){
    int u=Q.front();Q.pop();vis[u]=false;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
      int v=edge[i].to;
      if(dist[v]<dist[u]+edge[i].dis){
    dist[v]=dist[u]+edge[i].dis;
    if(!vis[v]){vis[v]=true;Q.push(v);}
      }
    }
  }
}
int main(){
  scanf("%d",&n);
  memset(head,-1,sizeof(head));
  for(int i=1;i<=n;i++){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    add(a-1,b,c);
  }
  add(50001,0,0);add(0,50001,-1);
  for(int i=1;i<=50000;i++){add(i-1,i,0);add(i,i-1,-1);}
  memset(dist,-0x5f,sizeof(dist));
  dist[50001]=0;
  SPFA();
  printf("%d
",dist[50000]);
  return 0;
}