poj 1201 Interval (查分约束)

时间:2022-04-14 07:55:02
/*
数组开大保平安.
查分约束:
输入的时候维护st和end
设每个点取元素di个 维护元素个数前缀和s
Sbi-Sai-1>=ci
即:建立一条从ai-1到bi的边 权值为ci 表示ai到bi的最小取元素个数
然后跑st到end的最长路 (建边就已经保证了最优)
最后 dis[end] 即为end的前缀和 即为st到end 符合每一个约束的最小去元素值
同时查分约束也满足性质 Sai-Sai-1>=0 Sai-1-Sai>=-1
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 500010
using namespace std;
int m,num,st=maxn,end,head[maxn],dis[maxn],f[maxn];
struct node
{
int v,t,pre;
}e[maxn];
int init()
{
int x=;char s;s=getchar();
while(s<''||s>'')s=getchar();
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x;
}
void Add(int from,int to,int dis)
{
num++;
e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void SPFA()
{
queue<int>q;
q.push(st);
f[st]=;
dis[st]=;
while(!q.empty())
{
int k=q.front();
q.pop();
f[k]=;
for(int i=head[k];i;i=e[i].pre)
if(dis[e[i].v]<dis[k]+e[i].t)
{
dis[e[i].v]=dis[k]+e[i].t;
if(f[e[i].v]==)
{
q.push(e[i].v);
f[e[i].v]=;
}
}
}
}
int main()
{
m=init();
int x,y,z;
for(int i=;i<=m;i++)
{
x=init();y=init();z=init();
Add(x,y+,z);
st=min(st,x);end=max(end,y+);
}
for(int i=st;i<=end;i++)
{
Add(i,i+,);
Add(i+,i,-);
}
memset(dis,-,sizeof(dis));
SPFA();
printf("%d\n",dis[end]);
return ;
}