我的第一道差分约束系统......刚开始有点摸不着头脑，搞清楚后发现完全就是套路...
题目大意：在线段[ai,bi]上至少选ci个点，使被选出的点的个数最少而且满足所有的限制条件，输出这个最小值。
分析：差分约束系统我就不在这里介绍啦~(≧▽≦)/~（这种东西网上一搜一大堆）
我们设s[i]表示区间[0,i]的整数个数，这道题的差分约束系统为：
s[b]-s[a-1]>=ci;
s[b]-a[b-1]>=0;
s[b-1]-s[b]>=-1。
然后我们再以ai-1或bi的值为结点，ci为权值连有向边，用SPFA求出从min跑到max的最长路就是答案啦。
至于为什么是最长路，不理解请自行跳转到此链接
ps.注意有向边的方向！！！
代码：
#include<cstdio> #include<algorithm> #include<cstring> const int maxn=5e5+5,inf=0x3f3f3f3f; using namespace std; struct point{ int next,w,to; }e[maxn*3]; int s,t,tot=0,first[maxn],minn=inf,maxx=0,q[maxn]; int dis[maxn]; bool vis[maxn]; int read() { int ans=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();} return ans*f; } void add(int u,int v,int wi) { tot++;e[tot].next=first[u];first[u]=tot;e[tot].to=v;e[tot].w=wi; } void spfa() { int head=0,tail=1; q[head]=minn;dis[minn]=0;vis[minn]=1; while(head!=tail){ int x=q[head];head++;if(head>=50000)head=0; for(int i=first[x];i;i=e[i].next){ int to=e[i].to; if(dis[to]<dis[x]+e[i].w){ dis[to]=dis[x]+e[i].w; if(!vis[to]){ vis[to]=1; q[tail]=to; tail++; if(tail>=50000)tail=0; } } } vis[x]=0; } } int main() { int n=read(),a,b,c; for(int i=1;i<=n;i++){ a=read();b=read();c=read(); add(a-1,b,c); minn=min(minn,a-1); maxx=max(maxx,b); } for(int i=minn;i<=maxx;i++){ add(i-1,i,0); add(i,i-1,-1); } memset(dis,-127,sizeof(dis)); memset(vis,0,sizeof(vis)); spfa(); printf("%d",dis[maxx]); return 0; }