POJ 1201 Interval （查分约束系统）

题意翻译

区间取数

题目描述

有n个区间，在区间[ai，bi]中至少取任意互不相同的ci个整数。求在满足n个区间的情况下，至少要取多少个正整数。

输入输出格式

输入格式

多组数据。

第一行的一个整数T表示数据个数。对于每组数据,第一行包含一个整数nn(11<=nn<=5000050000)表示区间数。以下nn行描述区间。输入的第(i+1)行包含三个整数ai，bi，ci，由空格分开。其中0<=ai<=bi<=50000，1<=ci<=bi-ai+1。

输出格式

对于每组数据，输出一个对于n个区间[ai，bi] 至少取ci个不同整数的数的总个数。

solution:  差分约束系统

对于一组不等式（n个未知数，m个不等式）：

x_i-x_j<=c_k

特点是全都是两个未知数的差小于等于某个常数（大于等于也可以，因为左右乘 −1就可以化成小于等于的形式），这样的不等式组称作差分约束系统。这个不等式组要么无解，要么就有无限组解。

差分约束系统的解法用到了单源最短路径问题中的三角形不等式。即对有向图中任意一条边 <u,v>都有： dis[v]≤dis[u]+len[u][v]，其中 dis[u] 和 dis[v] 是从源点分别到点 u和点 v 的最短路径的长度，len[u][v] 是边 <u,v> 的长度值。

这是显然的：如果存在顶点 u 到顶点 v 的有向边，那么从源点到顶点 v 的最短路径长度 小于等于从源点到顶点 u 的最短路径长度加上边 <u,v> 的长度值。

显然上述的不等式就是所描述的，也和差分约束系统中的不等式相同，因此就可以把差分约束系统转化成一张图。

构图：

每个未知数 xi 对应图中的一个顶点 vi ，把所有的不等式都化成图中的一条边，对于不等式 xi−xj≤y化成三角形不等式 xi≤xj+y就可以化成边 <vj,vi> 权值为 y 。最后在这张图上求一遍单源最短路，这些三角不等式就全部满足了，因为它是最短路问题的基本性质。

                     

 

以 1 为起点，则起点到各个顶点的最短距离为 dis[1]=0,dis[2]=0,dis[3]=5,dis[4]=4,dis[5]=1dis[1]=0,dis[2]=0,dis[3]=5,dis[4]=4,dis[5]=1 则得到解 x1=0,x2=1,x3=5,x4=4,x5=1x1=0,x2=1,x3=5,x4=4,x5=1

以 3 为起点，则起点到各个顶点的最短距离为 dis[1]=−5,dis[2]=−5,dis[3]=0,dis[4]=−1,dis[5]=−4dis[1]=−5,dis[2]=−5,dis[3]=0,dis[4]=−1,dis[5]=−4 则得到解 x1=−5,x2=−4,x3=0,x4=−1,x5=−4x1=−5,x2=−4,x3=0,x4=−1,x5=−4

以不同顶点作为起点会得到不同的解，但这些解都一定合理。

什么情况下无解？ 存在负权回路！

技巧：增加源点

具体实现时，往往在原图上附加一个顶点，这个顶点与每个顶点都连接一条权值为 0 的边

（以上内容部分转自） 

 

作者：寒江雪里独钓着的蓑笠翁 来源： 原文：https://blog.csdn.net/dragon60066/article/details/80245797 

---

 

下面是关于这道题的解决办法

做差分约束的体，我们要尽量多的找到条件，确保SPFA能正确转移（只要保证约束无误，列多了没事，列少了就会出错）

设dis[s]表示以[ 0, s ]中要选取的点的个数，那么在区间内的选的点的个数一定要大于要求的数量

并且dis[s]一定大于等于dis[s-1]，这是很显然的

综上所述，我们可以列出几个约束条件

1 dis[b]-dis[a-1]>=c ----> dis[b]>=dis[a-1]+c 2 dis[x]-dis[x-1]>=0 ----> dis[x]>=dis[x-1]+0 3 dis[x-1]-dis[x]>=-1 ----> dis[x-1]>=dis[x]-1

因此

add(i-1,i,0); add(i,i-1,-1); add(a-1,b,c）;

然后从最左端点开始跑SPFA（既可以求最短路又可以求最长路还能判负权边），输出dis[R]即可

code

#include<cstdio> #include<iostream> #include<queue> #include<cstring> #define maxn 160010 #define re register using namespace std; int L,R; int T,n,a,b,cnt,dis[maxn],vis[maxn],head[maxn],c; struct Edge{ int v,w,nxt; }e[maxn<<3]; inline void add(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].nxt=head[u]; head[u]=cnt; } queue<int>q; struct cmp{ bool operator ()(int &x,int &y) { return dis[x]<dis[y]; } }; void SPFA(int s) { memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0,vis[s]=1; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i;i=e[i].nxt) { int ev=e[i].v; if(dis[ev]<dis[now]+e[i].w) { dis[ev]=dis[now]+e[i].w; if(!vis[ev]) { vis[ev]=1; q.push(ev); } } } } } int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void clear() { memset(head,0,sizeof(head)); memset(e,0,sizeof e); L=maxn+10,R=-1; } int main() { T=read(); while(T--) { n=read(); clear(); for(re int i=1;i<=n;++i) { a=read(); b=read(); c=read(); add(a,b+1,c); L=min(a,L); R=max(R,b+1); //add(b+1,a,0) } for(re int i=L;i<=R;++i) { add(i,i+1,0); add(i+1,i,-1); } SPFA(L); printf("%d\n",dis[R]); } return 0; } //dis[b]-dis[a-1]>=c ----> dis[b]>=dis[a-1]+c //dis[x]-dis[x-1]>=0 ----> dis[x]>=dis[x-1]+0 //dis[x-1]-dis[x]>=-1 ----> dis[x-1]>=dis[x]-1

 

转载于:https://www.cnblogs.com/Liuz8848/p/10800702.html

相关资源：JAVA上百实例源码以及开源项目