『一本通』差分约束系统

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

总结

以上是生活随笔为你收集整理的『一本通』差分约束系统的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。