POJ1201Intervals(差分约束)
2024-10-01 16:14:48
题意
给出数轴上的n个区间[ai,bi],每个区间都是连续的int区间。
现在要在数轴上任意取一堆元素,构成一个元素集合V
要求每个区间[ai,bi]和元素集合V的交集至少有ci不同的元素
求集合V最小的元素个数。
题解
一眼望去差分约束。所以开始找约束条件。
设sum[i]为[1,i]闭区间的元素个数。
sum[b[i]]-sum[a[i]-1]>=c[i];
还有个隐含(显然)的约束条件:sum[i]-sum[i-1]>=0
然后跑最短路即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
struct edge{
int to,w,nxt;
}e[maxn*];
int n,cnt,head[maxn],dis[maxn],book[maxn];
void add(int u,int v,int w){
cnt++;
e[cnt].to=v;
e[cnt].nxt=head[u];
e[cnt].w=w;
head[u]=cnt;
}
void spfa(){
queue<int> q;
for(int i=;i<=;i++){
dis[i]=-;
}
book[]=;
q.push();
while(!q.empty()){
int u=q.front();
q.pop();
book[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(book[v]==){
book[v]=;
q.push(v);
}
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u+=;
v+=;
add(u-,v,w);
}
for(int i=;i<=;i++){
add(i-,i,);
add(i,i-,-);
}
spfa();
printf("%d",dis[]);
return ;
}
最新文章
- CSS Table Gallery
- java 模拟qq源码
- css+div
- ueditor-图片上传是报错
- html学习笔记1
- Windows Phone 8.1开发:如何从ListView中,获取ScrollViewer对象
- MySQL 线上配置文件
- 在QT程序中使用cout和cin
- 我对面向对象设计的理解——Java接口和Java抽象类
- mysql学习之check无效的解决及触发器的使用
- IDEA远程Debug
- 模拟获取post数据的方式
- SSH Secure Shell Client中文乱码的解决方法
- java——IObufferedReader文件输入输出流
- SpringBoot系列一:SpringBoot的产生
- Net系列框架-Dapper+简单三层架构
- node 加密音频文件 和 解密音频文件
- [二十七]SpringBoot 之 Restful接口的跨域请求
- 前端架构一之XAMPP
- 连接数据库的DBUtils工具类