POJ1201 Intervals [差分约束系统]
发布时间:2020-12-14 03:49:00 所属栏目:大数据 来源:网络整理
导读:题目传送门 Intervals Description You are given n closed,integer intervals [ai,bi] and n integers c1,...,cn.? Write a program that:? reads the number of intervals,their end points and integers c1,cn from the standard input,? computes the mi
题目传送门 IntervalsDescription
You are given n closed,integer intervals [ai,bi] and n integers c1,...,cn.?
Write a program that:? reads the number of intervals,their end points and integers c1,cn from the standard input,? computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai,bi],for each i=1,2,n,? writes the answer to the standard output.? Input
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai,bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai,n.
Sample Input 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output 6
Source
Southwestern Europe 2002
分析: 差分约束系统入门题。 以前没做过差分约束系统的题,来学习一下,大概是说在满足多个不等式的条件下求解某样东西时,可以把这些不等式转化成图论中求最短路的松弛公式然后把问题转换成求解最短(长)路。这道题就是一个很标准的差分约束系统。 要求满足的不等式包括$s[b[i]]-s[a[i]-1]geq c[i]$,$0leq s[i]-s[i-1]leq 1$,其中$s[i]$表示到第$i$个位置为止选择的点的个数,转换一下,就可以得到: $s[b[i]]geq s[a[i]-1]+c[i]$, $s[i]geq s[i-1]+0$, $s[i-1]geq s[i]+(-1)$, 这就得到了三种边权的边,就可以建图了。 Code: ? #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<queue> #include<iostream> #include<iomanip> #include<algorithm> #define Min(a,b) (a)<(b)?(a):(b) #define Max(a,b) (a)>(b)?(a):(b) using namespace std; const int N=5e4+7; int n,head[N],cnt,dis[N],ans,sta,ed; bool vis[N]; struct Node{ int to,val,nxt; Node(int x=0,int y=0,int z=0){ to=x,val=y,nxt=z; } }edge[N<<2]; queue<int>team; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){num=num*10+ch-‘0‘;ch=getchar();} return flag?-num:num; } inline void add(int x,int y,int z) { edge[++cnt]=Node(y,z,head[x]); head[x]=cnt; } void spfa() { memset(dis,-0x3f,sizeof(dis)); team.push(sta); vis[sta]=true;dis[sta]=0; int x,y; while(!team.empty()){ x=team.front();team.pop(); vis[x]=false; for(int i=head[x];i!=-1;i=edge[i].nxt){ y=edge[i].to; if(dis[y]<dis[x]+edge[i].val){ dis[y]=dis[x]+edge[i].val; if(!vis[y])team.push(y),vis[y]=true; } } } } int main() { n=read(); memset(head,-1,sizeof(head)); int a,b,c; sta=1e9,ed=-1; for(int i=1;i<=n;++i){ a=read(),b=read(),c=read(); add(a-1,c); sta=Min(sta,a-1);ed=Max(ed,b); } for(int i=sta;i<=ed;++i){ add(i-1,i,0); add(i,i-1,-1); } spfa(); printf("%d",dis[ed]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |