大致题意:
需要从0~50000内选一些整数点,给出m个约束条件,每个条件表述为,(s,t,c)表示在从s到t的区间内至少有c个点被选择。求最少选择多少个点。
大致思路:
转化为差分约束模型,设dis[i]为从0到i这个区间中被选择的点数。对每个约束,则有dis[t]-dis[s-1]>=c。另外还有一个隐含的约束条件就是0<=dis[i]-dis[i-1]<=1。另外要注意一点通过最短路径算法求出来的一组解当中,所有未知数都达到最大值。因为需要求的是最少加多少个点,所以要用spfa最长路。又由于最长路的三角形不等式为d(v) >= d(u) + w(u, v),所以这里就要按照大于等于关系来构图,最后得到的dis[n]就是答案。
详细代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=105000;
const int mMax=10000500;
const int inf=1<<28;
struct{
int v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int stack[nMax],m,sum[nMax];
bool vis[nMax];
void addedge(int a,int b,int w){
edge[k].w = w;
edge[k].v=b;
edge[k].next=head[a];
head[a]=k;k++;
}
bool spfa(int s){
int i, top = 0;
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)dis[i]=-inf;
dis[s]=0;
stack[++top]=s;
vis[s]=true;
while(top){
int u=stack[top--];
for(i=head[u];i!=0;i=edge[i].next){
int v=edge[i].v;
if(dis[v]<dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
if(++sum[v]>n)return 0;
}
}
}
vis[u]=false;
}
return 1;
}
int main(){
int m,s,t,c,i,j;
while(scanf("%d",&m)!=EOF){
k=1;
n=-1;
memset(sum,0,sizeof(sum));
memset(head,0,sizeof(head));
while(m--){
scanf("%d%d%d",&s,&t,&c);
// s++,t++;
n=max(n,t);
addedge(s-1,t,c);
}
s=n+2;
for(i=0;i<=n;i++){
addedge(i+1,i,-1);
addedge(i,i+1,0);
}
for(i=0;i<=n;i++){
addedge(s,i,0);
}
spfa(s);
cout<<dis[n]<<endl;
}
return 0;
}
分享到:
相关推荐
北大POJ1201-Intervals 解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1754756
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
这是西北工业大学的POJ试题的答案,欢迎下载!
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj分类poj分类poj分类poj分类
北大POJ1716-Integer Intervals【Difference Constraints】 解题报告+AC代码
POJ题目分类POJ题目分类POJ题目分类
poj 百练 题目分类 poj 百练 题目分类
poj上的测室数据,需要的下载........
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj题目分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
pojACM题目分类,便于各类型同学分别做题有所参考
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~