VIJOS 1540 月亮之眼
发布日期:2022-02-05 18:27:26 浏览次数:15 分类:技术文章

本文共 2350 字,大约阅读时间需要 7 分钟。

描述

吉儿是一家古董店的老板娘,由于她经营有道,小店开得红红火火。昨天,吉儿无意之中得到了散落民间几百年的珍宝—月亮之眼。吉儿深知“月亮之眼”价值连城:它是由许多珍珠相连而成的,工匠们用金线连接珍珠,每根金线连接两个珍珠;同时又对每根金线染上两种颜色,一半染成银白色,一半染成黛黑色。由于吉儿自小熟读古籍,所以还晓得“月亮之眼”的神秘传说:“月亮之眼”原是一个古代寺庙的宝物,原本是挂在佛堂的一根顶梁柱上的,整个宝物垂直悬挂,所有珍珠排成一线,且都镶嵌在柱子里,而每一根金线又都是绷紧的,并且金线的银白色一端始终在黛黑色一端的上方;然而,在一个月圆之夜,“月亮之眼”突然从柱里飞出,掉落下来,宝物本身完好无损,只是僧侣们再也无法以原样把“月亮之眼”嵌入柱子中了。吉儿望着这个神秘的宝物,回忆着童年读到的传说,顿时萌发出恢复“月亮之眼”的冲动,但是摆弄了几天依旧没有成功。

现在,要麻烦您来帮助吉儿完成这项使命。

您要设计一个程序,对于给定的“月亮之眼”进行周密分析,然后给出这串宝物几百年前嵌在佛堂顶梁柱上的排列模样。给定的“月亮之眼”有N个珍珠和P根金线,所有珍珠按一定顺序有了一个序号:1、2…、N。

格式

输入格式

输入数据包含一个“月亮之眼”的特征描述:

文件第一行有两个整数N和P,其中N表示宝物中的珍珠个数,P表示宝物中的金线根数;
以下P行描述珍珠连接情况:
文件第I+1行有三个整数,Ri1,Ri2,Li。其中Ri1表示第I根金线的银白色一端连接的珍珠序号;Ri2表示第I根金线的黛黑色一端连接的珍珠序号;Li表示第I根金线的长度。

输出格式

由于珍珠尺寸很小,所以几个珍珠可以同时镶嵌在一个位置上。

您的输出数据描述的是“月亮之眼”各个珍珠在顶梁柱上的位置,输出文件共N行:

第I行,一个整数S,它表示标号为I的珍珠在顶梁柱上距离最高位置珍珠的距离。

注意:若无解则输出仅一行,包含一个整数“-1”。

样例

样例输入

9 91 2 32 3 52 7 14 5 45 6 15 9 16 7 17 8 39 8 4

样例输出

2510045695

限制

1s

提示

N,P<=500

来源

Balkan OI 1998

CTSC 1999

一开始没看懂题

后来画个图就明白了

读入x,y,w

由于x必须在y上面

y必须在x下面

距离必须是w

所以建边(y,x,w) (x,y,-w)

类似于差分约束 不过要求必须线是直的 所以距离不等于w就要更新

我按不等于就更新写的 但是实际发现 跑最长路也可以 好奇妙的东西。。。。。。

#include
#include
#include
#include
using namespace std;const int lim=555;const int inf=999999999;struct self{int x,y,w;}s[lim<<2];int first[lim<<2],nxt[lim<<2];int d[lim];queue
q;bool inq[lim];int t[lim];int m,n,a,b,c,tall;bool spfa(){ int a; for(a=1;a<=m;a++)q.push(a); while(!q.empty()) { int u=q.front();q.pop();inq[u]=0; for(int e=first[u];e!=-1;e=nxt[e]) if(d[s[e].y]!=d[u]+s[e].w) { d[s[e].y]=d[u]+s[e].w; if(!inq[s[e].y]) { q.push(s[e].y); inq[s[e].y]=1; t[s[e].y]++; if(t[s[e].y]>m)return false; } } } return true;}int main(){ memset(first,-1,sizeof(first));memset(nxt,-1,sizeof(nxt)); scanf("%d%d",&m,&n); for(a=1;a<=n;a++) { scanf("%d%d%d",&s[a].y,&s[a].x,&s[a].w); nxt[a]=first[s[a].x];first[s[a].x]=a; s[a+n].x=s[a].y;s[a+n].y=s[a].x;s[a+n].w=-s[a].w; nxt[a+n]=first[s[a].y];first[s[a].y]=a+n; } if(!spfa()) { cout<<-1<<'\n'; return 0; } else { for(a=1;a<=m;a++)tall=max(tall,d[a]); for(a=1;a<=m;a++)cout<
<<'\n'; } return 0;}

转载地址:https://blog.csdn.net/li412302070/article/details/12782693 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VIJOS 1371 方程的解
下一篇:多米诺骨牌 DOMINO

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月10日 05时13分43秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql多维模型_数据仓库数据库设计方法---关系模型和多维模型比较分析 2019-04-21
局域网聊天程序 java MySQL_java 基于TCP/IP协议的局域网聊天小程序 2019-04-21
r glm 中的p值_假设检验中的P值 2019-04-21
mysql中sql语句结构_MySQL中使用sql语句获得表结构 2019-04-21
如何增加mysql主键约束_mysql修改表时怎么添加主键约束? 2019-04-21
java选择路径窗口_Java实现选择电脑路径的方法 2019-04-21
java 图像渐变_Java基础之在窗口中绘图——渐变填充(GradientApplet 1) 2019-04-21
冒泡排序面向对象java_所谓的面向对象实现的冒泡排序 2019-04-21
proto 客户端 JAVA_Kubernetes官方java客户端之五:proto基本操作 2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现 2019-04-21
java ajax 修改数据库数据库数据库_AJAX 自学练习 无刷新提交并修改数据库数据并显... 2019-04-21
java并发编程指南博客_Java并发编程-synchronized指南 2019-04-21
java怎么中断阻塞状态_java并发编程()阻塞方法与中断方法 2019-04-21
java zlib 位运算_位运算入门:找出一个二进制数的最右端的第一个1;计算一个二进制数中1的个数;找出数组中唯一一个出现次数为奇数的数;找出数组中唯二两个出现次数为奇数的数... 2019-04-21
java lua热更新_lua热更新学习 2019-04-21
script执行php文件_php命令行(cli)下执行PHP脚本文件的相对路径的问题解决方法... 2019-04-21
apache 2.4 php5.4_apache2.4+php5.4+my sql 5.6,网站经常无故不能访问 2019-04-21
php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
java blockingqueue源码_Java并发队列BlockingQueue实现之ArrayBlockingQueue源码分析 2019-04-21