poj 1716 Integer Intervals(差分约束)
2024-10-08 02:33:59
跟之前个人赛的一道二分加差分约束差不多,也是求满足条件的最小值。
题意是,给出若干区间,需要找出最少的元素个数,使得每个区间至少包含两个这里的元素。
做法就是建立(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
最新文章
- Spark MLlib 之 Naive Bayes
- REST服务中的异常处理
- Git基本常用命令
- .Net SqlDbHelper
- python数字图像处理(6):图像的批量处理
- HD 2177(威佐夫博弈 入门)
- changing a pointer rather than erasing memory cells
- [HIHO119]网络流五&#183;最大权闭合子图(最大流)
- Airbnb面试的27个奇葩问题,你 hold 住吗?
- Editplus 中将文本换行替换为<;p>;标签的正则表达式
- 你不需要jQuery
- 利用Ajax改变发送请求方式
- Object-C 函数定义 -- 笔记
- 微信订阅号开发之token验证后,自动回复消息功能做好,发送消息没有返回
- Dreamweaver显示花括号匹配
- idea 查看tomcat源码
- 洛谷 P3410 拍照
- 【SQL】面面俱到 | 在SQL中使用CUBE和ROLLUP实现数据多维汇总
- 实战 | Android中文图混排时文图的居中对齐 FontMetrics以及自定义ImageSpan实现
- pandas中遍历dataframe的每一个元素