HDU1384 差分约束
Intervals
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4028 Accepted Submission(s): 1530
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
Process to the end of file.
有一个序列,题目用n个整数组合 [ai,bi,ci]来描述它,[ai,bi,ci]表示在该序列中处于[ai,bi]这个区间的整数至少有ci个。如果存在这样的序列,请求出满足题目要求的最短的序列长度是多少。
输入:第一行包括一个整数n,表示区间个数,以下n行每行描述这些区间,第i+1行三个整数ai,bi,ci,由空格隔开,其中0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1。
输出:一行,输出满足要求的序列的长度的最小值。
思路:
显然有不等式Bi-A(i-1)>=Ci (A,B是两个端点),又因为如果从0点到x点有y个那么从0点到x+1点可能有y个也可能有y+1个,即相邻的两点之间可能增加一个也可能没有增加又得出两个不等式:Ai-A(i-1)>=0,Ai-A(i-1)<=1;得到三个约束条件:Bi-A(i-1)>=Ci ,Ai-A(i-1)>=0 ,A(i-1)-Ai>=-1; 依据b-a>=c建立一条从a到b的有向边,权值为c。
这样就有了要满足dis[v]>=dis[u]+w的不等式类似求最短路的spfa中dis[v]>dis[u]+w的松弛,因此起点到终点最小的序列长度就是求得起点的单源最短路中到终点的距离。
a,b,从0开始a-1会出现负数所以a++;b++;
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=,inf=0x7fffffff;
struct node
{
int to,next,val;
} edge[maxn*];
int mark[maxn],head[maxn],tot,src,dis[maxn],n,Min,Max;
void add(int a,int b,int c)
{
edge[tot].to=b;
edge[tot].next=head[a];
edge[tot].val=c;
head[a]=tot++;
}
void spfa(int s)
{
for(int i=Min;i<=Max;i++)
dis[i]=-inf;
memset(mark,,sizeof(mark));
queue<int>q;
dis[s]=;
mark[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
mark[u]=;
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]<dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!mark[v])
{
q.push(v);
mark[v]=;
}
}
}
}
}
main()
{
while(scanf("%d",&n)==){
int a,b,c;
memset(head,-,sizeof(head));
tot=;
for(int i=;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
a++;b++;
Min=min(Min,a-);
Max=max(Max,b);
add(a-,b,c);
}
for(int i=Min;i<=Max;i++){
add(i-,i,);
add(i,i-,-);
}
spfa(Min);
printf("%d\n",dis[Max]);
}
return ;
}
最新文章
- xml schema xmlns xmlns:xsi xsi:schemaLocation targetnamespace
- python函数和常用模块(二),Day4
- SpringMVC Controller介绍(转)
- java编写二叉树以及前序遍历、中序遍历和后序遍历 .
- python模块之time和datetime
- Google 高性能 RPC 框架 gRPC 1.0.0 发布(附精彩评论)
- 关于 table-layout 属性
- 几种经典排序算法的JS实现
- 慕课网-前端JavaScrpt基础面试技巧-学习笔记
- shell中冒号 : 用途说明
- Eureka介绍
- input清空和select重置
- Scrapy运行流程
- React-Route的属性exact
- 18.搭建 vue 环境
- 【JS】【3】标签显示几秒后自动隐藏
- Activiti任务认领
- 2019.01.21 洛谷P3919 【模板】可持久化数组(主席树)
- Why is long2ip conversion important?
- 用递归方法求 n!