POJ 1364 King 题解与分析

2024-06-07 07:18
文章标签 分析 poj 题解 king 1364

本文主要是介绍POJ 1364 King 题解与分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

King
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 9040 Accepted: 3395

Description

对题目中给定的si,ni,ki,和一个给定的序列S[1....N],如果格式为(si,ni,gt,ki),意思就是新增一约束条件S[si]+S[si+1]+...S[si+ni]>ki,如果格式为(si,ni,lt,ki),意思就是新增一约束条件S[si]+S[si+1]+...S[si+ni]<ki,判断所给的约束条件有符合要求的序列S[1....N],有解就输出lamentable kingdom,无解就输出successful conspiracy。

Sample Input

4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0

Sample Output

lamentable kingdom
successful conspiracy
 
【分析】:
    设a[i]表示∑a[k],k∈[1,i]且k∈Z*,那么对于约束条件S[si]+S[si+1]+...S[si+ni]>ki可转变为a[si+ni]-a[si-1]>ki(因为要包含[si,si+ni],因此根据a数组的定义,下限为a[si-1]),而差分约束系统只能解形如Ax≤b的不等式组,因此转化给出的约束条件S[si]+S[si+1]+...S[si+ni]>ki→a[si+ni]-a[si-1]>ki→a[si-1]-a[si+ni]<=-ki-1,另一个同理:a[si+ni]-a[si-1]<=ki-1,然后跑一边差分约束即可<这里用的是spfa+邻接表存储>
【基础理论】:差分约束系统,用最短路算法实现
【代码】:
/*
Problem: 1364  User: csyzcyj 
Memory: 192K  Time: 0MS 
Language: C++  Result: Accepted 
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define MAX 201
#define MAXP 1001
#define IMAX 21474836
struct EDGE{int to,next,v;};
EDGE a[MAXP];
int N,M,tot=0,last[MAX],dist[MAX],tot1[MAX];     
bool vis[MAX];
void add(int x,int y,int value)
{
a[++tot].to=y;
a[tot].next=last[x];
a[tot].v=value;
last[x]=tot;
}
bool check()
{
queue<int> Q;
memset(dist,0,sizeof(dist));
for(int i=0;i<=N;i++)
Q.push(i);
while(!Q.empty())
{
int now=Q.front();
Q.pop();
vis[now]=false;
for(int i=last[now];i!=-1;i=a[i].next)
{
int now_to=a[i].to;
if(dist[now]+a[i].v<dist[now_to])
{
dist[now_to]=dist[now]+a[i].v;
if(!vis[now_to])
{
vis[now_to]=true;
tot1[now_to]++;
if(tot1[now_to]>N)   return false;   
Q.push(now_to);
}
} 
}
}
return true;
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout); 
while(scanf("%d%d",&N,&M)!=EOF && N!=0 && M!=0)
{
memset(last,-1,sizeof(last));      
memset(vis,true,sizeof(vis));
memset(tot1,0,sizeof(tot1));
memset(a,0,sizeof(a));
tot=0;
for(int i=1;i<=M;i++)
{
int A,B,C;
char ch1,ch2;
scanf("%d%d",&A,&B);
scanf("%c%c%c",&ch1,&ch1,&ch2);
scanf("%d",&C);
if(ch1=='g')
add(A+B,A-1,-C-1);
if(ch1=='l')
add(A-1,A+B,C-1);
}
if(check())   printf("lamentable kingdom\n");
else    printf("successful conspiracy\n");
}
//system("pause");
return 0;
}

 

转载注明出处:http://blog.csdn.net/u011400953

 


                                    

这篇关于POJ 1364 King 题解与分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1038507

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

java -jar命令运行 jar包时运行外部依赖jar包的场景分析

《java-jar命令运行jar包时运行外部依赖jar包的场景分析》:本文主要介绍java-jar命令运行jar包时运行外部依赖jar包的场景分析,本文给大家介绍的非常详细,对大家的学习或工作... 目录Java -jar命令运行 jar包时如何运行外部依赖jar包场景:解决:方法一、启动参数添加: -Xb