差分约束不用判负环
设 $s[i]$ 为 0~i 中选了几个数
根据题意 $s[bi]-s[ai-1]>=ci$,
根据实际意义每个点最多选一个数 $s[i+1]-s[i]>=0,s[i+1]-s[i]<=1$
从最小值跑到最大值
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- using namespace std;
- const int maxn=50009;
- const int inf=1e9+7;
- struct node{
- int v,w,nxt;
- }e[maxn*3];
- int head[maxn],d[maxn],vis[maxn],cnt,n,mn,mx;
- void add(int u,int v,int w){
- e[++cnt].v=v;
- e[cnt].nxt=head[u];
- e[cnt].w=w;head[u]=cnt;
- }
- void spfa(){
- for(int i=mn;i<=mx;i++)d[i]=-inf;
- d[mn]=0;queue<int>q;
- q.push(mn);
- while(!q.empty()){
- int x=q.front();q.pop();vis[x]=0;
- for(int i=head[x];i;i=e[i].nxt){
- int y=e[i].v;
- if(d[y]<d[x]+e[i].w){
- d[y]=d[x]+e[i].w;
- if(!vis[y])q.push(y),vis[y]=1;
- }
- }
- }
- }
- int main(){
- while(~scanf("%d",&n)){
- cnt=0;
- memset(head,0,sizeof(head));
- memset(vis,0,sizeof(vis));
- memset(e,0,sizeof(e));
- for(int i=0,u,v,w;i<n;i++){
- scanf("%d%d%d",&u,&v,&w);
- add(u,v+1,w);
- mn=min(mn,u);
- mx=max(mx,v+1);
- }
- for(int i=mn;i<mx;i++){
- add(i,i+1,0);add(i+1,i,-1);
- }
- spfa();
- printf("%d",d[mx]);
- }
- }
[题解 / 模板]POJ_1201(差分约束
来源: http://www.bubuko.com/infodetail-3216496.html