洛谷P1250 种树 && POJ1201 Intervals

洛谷P1250 种树-链接

POJ1201 Intervals-链接

差分约束，取最长路。

注意隐藏条件：因为对于第i个点有选择和不选择两种情况，所以\(0<=sum[i]-sum[i-1]<=1\)

//POJ代码，洛谷的只需要把define N改成读入N
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 50005
#define N 50005

int dis[MAXN],vis[MAXN],head[MAXN];
struct edge{
	int v,w,next;
	edge():next(0){}
}G[MAXN<<2];
int h,tot=0;
std::queue<int>que; 
inline void add(int u,int v,int w){
	G[++tot].v=v;G[tot].w=w;G[tot].next=head[u];head[u]=tot;
}

int main(){

	scanf("%d",&h);
	
	std::memset(dis,-1,sizeof(dis));
	std::memset(vis,0,sizeof(vis));
	std::memset(head,0,sizeof(head));
	
	for(register int i=1;i<=h;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u-1,v,w);
	}	
	for(register int i=0;i<N;++i){
		add(i,i+1,0);
	}
	for(register int i=1;i<=N;++i){
		add(i,i-1,-1);
	}
		
	dis[0]=0;
	que.push(0);
	vis[0]=1;
	while(!que.empty()){
			
		int u = que.front();
		que.pop();
			
		for(register int j=head[u];j;j=G[j].next){
			int v = G[j].v;
			if(dis[v]<dis[u]+G[j].w){
				dis[v] = dis[u]+G[j].w;
				if(vis[v]==0){
					vis[v] = 1;
					que.push(v);
				}
			}
		}
		vis[u] = 0;
	}
	
	printf("%d",dis[N]);
	return 0;
}