正題

題目鏈接:http://poj.org/problem?id=1201

---

題目大意

求一個最少數量的數字集合滿足

在$l_i～r_i$的范圍的數字至少是$c_i$個

---

解題思路

設$s_i$表示$0～i$的范圍內數字個數。然后其實條件就是$s_r?s_i\ge c$。然后就是差分約束。

但是需要注意$s_i?s_{i?1}\le 1$且$s_i?s_{i?1}\ge 0$這兩個隱藏條件。

---

$code$

#include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=50100; struct node{int to,next,w; }a[N*4]; int tot,ls[N],f[N],n,m; bool v[N]; queue<int> q; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void spfa() {memset(f,0xcf,sizeof(f));q.push(1);v[1]=1;f[1]=0;while(!q.empty()){int x=q.front();q.pop();v[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w>f[y]){f[y]=f[x]+a[i].w;if(!v[y]){v[y]=1;q.push(y);}}}} } int main() {n=50000;scanf("%d",&m);for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);x+=2;y+=2;addl(x,y+1,w);}for(int i=2;i<=n+2;i++)addl(i-1,i,0),addl(i,i-1,-1);spfa();printf("%d",f[n+2]); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的POJ1201-Intervals【差分约束,负环,SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。