首页 > 代码库 > POJ1201:Intervals【差分约束】
POJ1201:Intervals【差分约束】
题目大意:给出N个闭区间,每个区间给出一个ci值,让你找出最小的数集Z使得每个闭区间都有不少于ci个Z中的元素,求card(Z)
思路:06年集训队论文《浅析差分约束系统》有详细的解题,设Sn为[0,n]中Z中元素的个数,ai ,bi为区间的两个端点,则可列出以下不等式:
0<=Sn-S(n-1)<=1
S(bi+1)-S(ai)>=ci
然后就可以用差分约束做了,顺便提一下,如果要把0<=Sn-S(n-1)<=1这些边加进图中的话边集会非常的大,以至于一开始邻接表开50000时TLE 130000 RE 140000 WA 一直开到150000才AC
#include<cstdio>#include<algorithm>#include<queue>#include<string.h>#include<iostream>#define maxn 150010using namespace std;int head[maxn],point[maxn],next[maxn],value[maxn],dist[maxn];int now=0,minx=19941117,maxx=-19941117;queue<int> q;void add(int x,int y,int c){ next[++now]=head[x]; head[x]=now; point[now]=y; value[now]=c;}void spfa(int s){ int u; bool visit[maxn]={0}; for(int i=minx;i<=maxx;i++)dist[i]=-19941117; q.push(s); visit[s]=1; dist[s]=0; while(!q.empty()) { u=q.front(); q.pop(); visit[u]=0; for(int i=head[u];i!=0;i=next[i]) { int k=point[i]; if (dist[u]+value[i]>dist[k]) { dist[k]=dist[u]+value[i]; if (visit[k]==0) { visit[k]=1; q.push(k); } } } }}int main(){ int n,a,b,c; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); if (b+1>maxx)maxx=b+1; if (a<minx)minx=a; add(a,b+1,c); } for(int i=minx;i<=maxx;i++) { add(i,i+1,0); add(i+1,i,-1); } spfa(minx); printf("%d\n",dist[maxx]); return 0;}
POJ1201:Intervals【差分约束】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。