1716 -- Integer Intervals

  跟之前个人赛的一道二分加差分约束差不多,也是求满足条件的最小值。

  题意是,给出若干区间,需要找出最少的元素个数,使得每个区间至少包含两个这里的元素。

  做法就是建立(b)->(a)=-2,(i)->(i+1)=1,(i+1)->(i)=0的边,然后跑一次spfa即可。

  做完的时候,因为队列开太小,所以re了一次。

代码如下:

 #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
struct Edge {
int t, nx, c;
Edge() {}
Edge(int t, int nx, int c) : t(t), nx(nx), c(c) {}
} edge[N << ];
int eh[N], ec; void init() {
memset(eh, -, sizeof(eh));
ec = ;
} void addedge(int s, int t, int c) {
edge[ec] = Edge(t, eh[s], c);
eh[s] = ec++;
} int q[N << ], dis[N];
bool vis[N]; int spfa(int s, int t) {
memset(vis, , sizeof(vis));
memset(dis, , sizeof(dis));
int qh, qt, cur;
qh = qt = ;
q[qt++] = s;
vis[s] = true;
dis[s] = ;
while (qh < qt) {
//cout << cur << endl;
cur = q[qh++];
vis[cur] = false;
for (int i = eh[cur]; ~i; i = edge[i].nx) {
//cout << i << endl;
Edge &e = edge[i];
if (dis[e.t] > dis[cur] + e.c) {
dis[e.t] = dis[cur] + e.c;
q[qt++] = e.t;
vis[e.t] = true;
}
}
}
return dis[t];
} int main() {
int n, x, y;
while (~scanf("%d", &n)) {
init();
int mn = , mx = -;
for (int i = ; i < n; i++) {
scanf("%d%d", &x, &y);
addedge(y + , x, -);
mn = min(mn, x);
mx = max(mx, y + );
}
for (int i = ; i <= ; i++) {
addedge(i, i + , );
addedge(i + , i, );
}
printf("%d\n", -spfa(mx, mn));
}
return ;
}

——written by Lyon

最新文章

  1. Spark MLlib 之 Naive Bayes
  2. REST服务中的异常处理
  3. Git基本常用命令
  4. .Net SqlDbHelper
  5. python数字图像处理(6):图像的批量处理
  6. HD 2177(威佐夫博弈 入门)
  7. changing a pointer rather than erasing memory cells
  8. [HIHO119]网络流五&#183;最大权闭合子图(最大流)
  9. Airbnb面试的27个奇葩问题,你 hold 住吗?
  10. Editplus 中将文本换行替换为&lt;p&gt;标签的正则表达式
  11. 你不需要jQuery
  12. 利用Ajax改变发送请求方式
  13. Object-C 函数定义 -- 笔记
  14. 微信订阅号开发之token验证后,自动回复消息功能做好,发送消息没有返回
  15. Dreamweaver显示花括号匹配
  16. idea 查看tomcat源码
  17. 洛谷 P3410 拍照
  18. 【SQL】面面俱到 | 在SQL中使用CUBE和ROLLUP实现数据多维汇总
  19. 实战 | Android中文图混排时文图的居中对齐 FontMetrics以及自定义ImageSpan实现
  20. pandas中遍历dataframe的每一个元素

热门文章

  1. Django--多对多表的创建、contentType、ajax、ajax传输json数据格式、ajax传输文件数据、 自定义分页器
  2. python基--re模块的使用
  3. Spring Boot邮件功能
  4. day38 03-Spring的IOC和DI的区别
  5. NKOJ1472 警卫安排
  6. 关闭防火墙,仍然无法访问80端口 centos
  7. windows上安装Anaconda和python的教程详解
  8. 《2019年上半年Web应用安全报告》发布:90%以上攻击流量来源于扫描器,IP身份不再可信
  9. linux下播放器设计和开发
  10. qbao