大致题意:
告诉你有一列长度为n的数列和m个关系式。每个关系式的表述为:
si ni “gt” c 或者是 si ni “lt” c。分别代表该数列第si项一直加到第si+ni项的和大于c,和第si项一直加到第si+ni项的和小于c。求是否存在满足以上m个要求的数列。是则输出“lamentable kingdom”,否则输出“successful conspiracy”。
大致思路:
把问题转化为差分约束。将差分约束系统中的点sum[i]设为这个数列前i项的和。当要求第si项一直加到第si+ni项的和大于c的时候,就等价于sum[si+ni]-sum[si-1]>c,又由于差分约束系统中只能出现<=关系且这里的数字都是整数,所以上式又可以转化为sum[i-1]-sum[i+n]<=-c-1。
对于“第si项一直加到第si+n项的和小于c”的要求,我们同样可以将其转化为sum[si+ni]-sum[si-1]<=c-1;
按照得到的式子构出差分约束系统,用spfa判断是否存在可行解即可。
详细代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=1050;
const int mMax=1000050;
const int inf=1<<28;
struct{
int v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax],issea[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){
// cout<<top<<endl;
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;
// cout<<v<<" "<<sum[v]<<endl;;
}
}
}
vis[u]=false;
}
return 1;
}
int main(){
int i,j,si,ni,c,s;
char str[10];
while(scanf("%d",&n)!=EOF&&n){
scanf("%d",&m);
k=1;
s=n+2; //s作为加入差分约束系统的“虚拟点”
memset(head,0,sizeof(head));
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++){
addedge(s,i,0);
}
while(m--){
scanf("%d%d%s%d",&si,&ni,str,&c);
if(str[0]=='g'){
addedge(si+ni,si-1,-c-1);
}
else{
addedge(si-1,si+ni,c-1);
}
}
if(spfa(s)){
printf("lamentable kingdom\n");
}
else{
printf("successful conspiracy\n");
}
}
return 0;
}
分享到:
相关推荐
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分类
POJ题目分类POJ题目分类POJ题目分类
poj 百练 题目分类 poj 百练 题目分类
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj题目分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
pojACM题目分类,便于各类型同学分别做题有所参考
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
史上最全poj题目分类(159页).pdf
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为: