POJ1201 Intervals(差分约束)
2018-06-17 21:07:57来源:未知 阅读 ()
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 28416 | Accepted: 10966 |
Description
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
Output
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6
Source
$S\left[ i-1\right] -S\left[ i\right] \geq -1$
#include<cstdio> #include<queue> #include<cstring> #define INF 1e8+10 using namespace std; const int MAXN=1e6+10; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++) char buf[MAXN],*p1=buf,*p2=buf; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN],num=1; int maxx=-INF,minn=INF; int dis[MAXN],vis[MAXN]; inline void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int SPFA() { queue<int>q; memset(dis,-0xf,sizeof(dis)); dis[minn]=0;q.push(minn); while(q.size()!=0) { int p=q.front();q.pop(); vis[p]=0; for(int i=head[p];i!=-1;i=edge[i].nxt) { if(dis[edge[i].v]<dis[p]+edge[i].w) { dis[edge[i].v]=dis[p]+edge[i].w; if(vis[edge[i].v]==0) vis[edge[i].v]=1,q.push(edge[i].v); } } } printf("%d",dis[maxx]); } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); int N=read(); for(int i=1;i<=N;i++) { int x=read(),y=read(),z=read(); AddEdge(x,y+1,z); maxx=max(y+1,maxx); minn=min(x,minn); } for(int i=minn;i<=maxx-1;i++) { AddEdge(i+1,i,-1); AddEdge(i,i+1,0); } SPFA(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:使用sstream来进行类型转换
下一篇:HDU1878 欧拉回路
- P2352 队爷的新书(差分) 2019-10-28
- P3028 汽水机(差分) 2019-10-28
- 差分约束系统个人理解 2018-06-18
- 浅谈差分约束系统——图论不等式的变形 2018-06-17
- P3368 【模板】树状数组 2(树状数组维护差分序列) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash