首页 > 代码库 > POJ 1716 Interger Intervals 差分约束(入门题)
POJ 1716 Interger Intervals 差分约束(入门题)
题意:给出n个区间[a,b] n,a,b<=1e4,要求找到一个最小集合 使得每个区间至少有两个数在集合中.
设d[i]为0~i中有多少个元素在集合中,mn,mx分别为左右端点
则对每个i=1..n都要满足 d[b[i]]-d[a[i]-1]>=2
保证等式有意义,d[i+1]<=d[i]+1 , d[i]<=d[i+1]
全部化为小于号 d[a[i]-1]-d[b[i]]<=-2
若答案为ans 则d[mx]-d[mn-1]>=ans
把mx当作源点,求出到mn-1的最短路即为ans
由最短路的三角形不等式 d[v]<=d[u]+w 即 d[v]-d[u]<=w
则按照上面方式建图,求出最短路的同时,也满足了所有的约束条件
#include <iostream> #include <queue> #include <cstring> #include <cmath> #include <cstdio> #include <vector> using namespace std; typedef pair<int,int> ii; const int N=5e5+20; const int inf=1e9; struct node{ int to,next,w; }e[N]; int head[N],cnt; void insert(int u,int v,int w) { e[cnt].to=v,e[cnt].w=w,e[cnt].next=head[u]; head[u]=cnt++; } int n,inq[N],d[N]; queue<int> q; void SPFA(int s,int t) { while(!q.empty()) q.pop(); for(int i=0;i<=s;i++) inq[i]=0,d[i]=inf; q.push(s); inq[s]=1,d[s]=0; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to,w=e[i].w; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!inq[v]) inq[v]=1,q.push(v); // cout<<v<<‘ ‘<<d[v]<<endl; } } } cout<<d[s]-d[t]<<endl; } int main() { int w=2,a,b; while(cin>>n) { //d[b]-d[a-1]>=2 //d[a-1]<=d[b]+(-2) cnt=0; memset(head,-1,sizeof(head)); int mx=-inf,mn=inf; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); insert(b+1,a,-2); mx=max(mx,b+1),mn=min(mn,a); } //d[i+1]<=d[i]+1 //d[i]<=d[i+1] for(int i=0;i<mx;i++) insert(i,i+1,1),insert(i+1,i,0); // cout<<mx<<‘ ‘<<mn-1<<endl; SPFA(mx,mn); } return 0; }
POJ 1716 Interger Intervals 差分约束(入门题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。