loj10087 Intervals

传送门

分析

我们设S[i]表示到第i个数为止一共有多少个数在集合Z之中，最终答案就是S[max]-S[min]的最小值。所以我们不难发现对于每一个[ai,bi]都表示S[bi]-S[ai-1]>=ci，而我们又知道0<=S[i]-S[i-1]<=1，所以建图策略便是每一个ai向bi连一条权值为ci的边，i-1向i连一条权值为0的边，i向i-1连一条权值为-1的边，然后跑最长路就可以了。注意在代码中为了方便起见所有的值i向后移了一位。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<pair<int,int> >v[50040];
int d[50040],iq[50040];
queue<int>q;
inline void spfa(int s){
      memset(d,-1,sizeof(d));
      memset(iq,0,sizeof(iq));
      q.push(s);d[s]=0;iq[s]=1;
      while(!q.empty()){
          int x=q.front();
          q.pop();iq[x]=0;
          for(int i=0;i<v[x].size();i++){
            int y=v[x][i].first,z=v[x][i].second;
            if(d[y]<d[x]+z){
                d[y]=d[x]+z;
                if(!iq[y]){
                  q.push(y);
                  iq[y]=1;
                }
            }
          }
      }
      return;
}
int main(){
      int n,m,i,j,k,s=inf,t=-1;
      scanf("%d",&n);
      for(i=1;i<=n;i++){
          int x,y,z;
          scanf("%d%d%d",&x,&y,&z);
          y++;
          v[x].push_back(make_pair(y,z));
          s=min(s,x),t=max(t,y);
      }
      for(i=s;i<t;i++){
          v[i].push_back(make_pair(i+1,0));
          v[i+1].push_back(make_pair(i,-1));
      }
      spfa(s);
      printf("%d
",d[t]);
        return 0;
}