SP116 INTERVAL - Intervals

本文主要是介绍SP116 INTERVAL - Intervals，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

.
.
.
.
.
分析
差分约束+spfa

.
.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;struct edge
{int to,from,v;
}e[800010];int dis[400010],head[400010],cnt=1,bz[400010];
bool f[400010];void insert(int x,int y,int v)
{e[++cnt].to=y;e[cnt].from=head[x];e[cnt].v=v;head[x]=cnt;
}void spfa(int x)
{queue<int>q;memset(dis,-1,sizeof(dis));memset(f,false,sizeof(f));f[x]=true;dis[x]=0;q.push(x);while (!q.empty()){int u=q.front();q.pop();f[u]=false;for (int i=head[u];i;i=e[i].from)if (dis[e[i].to]<dis[u]+e[i].v){dis[e[i].to]=dis[u]+e[i].v;if (!f[e[i].to]){f[e[i].to]=true;q.push(e[i].to);}}}
}int main()
{int t;scanf("%d",&t);while (t--){memset(e,0,sizeof(e));memset(head,0,sizeof(head));int n,tj=-2147483647;cnt=0;scanf("%d",&n);for (int i=1;i<=n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);insert(a,b+1,c);tj=max(tj,b);}for (int i=1;i<=tj+1;i++){insert(i-1,i,0);insert(i,i-1,-1);}spfa(0);printf("%d\n",dis[tj+1]);}return 0;
}

这篇关于SP116 INTERVAL - Intervals的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---