Intervals

設$s[k]$表示$0$~$k$之間最少選出多少個整數。

由題得$s[b_i]-s[a_i-1]\ge c_i$，$0\le s[k+1]-s[k] \le 1$ 。

根據關系式連邊，$SPFA$ 跑一遍 最長路 即可。

#include<bits/stdc++.h> using namespace std; const int N=5e4+5; int n,cnt,Min,Max,fro[N],dis[N]; bool vis[N]; struct edge{int to,w,nxt;}e[N<<2]; queue<int> q; void add(int x,int y,int z) {e[++cnt].to=y,e[cnt].w=z,e[cnt].nxt=fro[x]; fro[x]=cnt; }int SPFA() {memset(dis,-0x3f,sizeof(dis));dis[Min]=0,vis[Min]=1;q.push(Min);while(!q.empty()) {int u=q.front();q.pop(),vis[u]=0;for(int i=fro[u];i;i=e[i].nxt) {int v=e[i].to;if(dis[v]<dis[u]+e[i].w) {dis[v]=dis[u]+e[i].w;if(!vis[v]) vis[v]=1,q.push(v);}}}return dis[Max]; }int main() {scanf("%d",&n);int a,b,c;Min=N+1,Max=-1;for(int i=1;i<=n;i++) {scanf("%d%d%d",&a,&b,&c);add(a-1,b,c);Min=min(Min,a-1),Max=max(Max,b);}for(int i=Min;i<=Max;i++) add(i,i+1,0),add(i+1,i,-1);printf("%d",SPFA()); }

?

轉載于:https://www.cnblogs.com/qq8260573/p/10387599.html

總結

以上是生活随笔為你收集整理的『一本通』差分约束系统的全部內容，希望文章能夠幫你解決所遇到的問題。

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