首页 > 代码库 > （差分约束） hdu 1384
（差分约束） hdu 1384
Intervals
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3038 Accepted Submission(s): 1118
Problem 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 endpoints 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
Write a program that:
> reads the number of intervals, their endpoints 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 <= 50 000) - 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 <= 50 000 and 1 <= ci <= bi - ai + 1.
Process to the end of file.
Process to the end of file.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.
Sample Input
53 7 38 10 36 8 11 3 110 11 1
Sample Output
6
Author
1384
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<string>#include<cmath>#include<algorithm>#include<vector>#include<queue>using namespace std;#define INF 0xfffffffvector<int> e[50001],w[50001];queue<int> q;int n,dist[50001],r,l,vis[50001];void addedge(int a,int b,int c){ e[b].push_back(a); w[b].push_back(c);}void SPFA(){ int x; vis[r]=1; q.push(r); while(!q.empty()) { x=q.front(),q.pop(); vis[x]=0; for(int i=0;i<e[x].size();i++) { if(dist[x]+w[x][i]<dist[e[x][i]]) { dist[e[x][i]]=dist[x]+w[x][i]; if(!vis[e[x][i]]) { vis[e[x][i]]=1; q.push(e[x][i]); } } } }}int main(){ while(scanf("%d",&n)!=EOF) { int a,b,c; l=INF,r=0; for(int i=0;i<50001;i++) { vis[i]=0; e[i].clear(),w[i].clear(); dist[i]=INF; } for(int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a-1,b,-c); if(a<l) l=a; if(b>r) r=b; } l--; for(int i=l;i<r;i++) { addedge(i+1,i,1); addedge(i,i+1,0); } dist[r]=0; while(!q.empty()) q.pop(); SPFA(); printf("%d\n",-dist[l]); } return 0;}
（差分约束） hdu 1384
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。