首页 > 代码库 > 月亮之眼
月亮之眼
Description
吉儿是一家古董店的老板娘，由于她经营有道，小店开得红红火火。昨天，吉儿无意之中得到了散落民间几百年的珍宝—月亮之眼。吉儿深知“月亮之眼”价值连城：它是由许多珍珠相连而成的，工匠们用金线连接珍珠，每根金线连接两个珍珠；同时又对每根金线染上两种颜色，一半染成银白色，一半染成黛黑色。由于吉儿自小熟读古籍，所以还晓得“月亮之眼”的神秘传说：“月亮之眼”原是一个古代寺庙的宝物，原本是挂在佛堂的一根顶梁柱上的，整个宝物垂直悬挂，所有珍珠排成一线，且都镶嵌在柱子里，而每一根金线又都是绷紧的，并且金线的银白色一端始终在黛黑色一端的上方；然而，在一个月圆之夜，“月亮之眼”突然从柱里飞出，掉落下来，宝物本身完好无损，只是僧侣们再也无法以原样把“月亮之眼”嵌入柱子中了。吉儿望着这个神秘的宝物，回忆着童年读到的传说，顿时萌发出恢复“月亮之眼”的冲动，但是摆弄了几天依旧没有成功。 现在，要麻烦您来帮助吉儿完成这项使命。 您要设计一个程序，对于给定的“月亮之眼”进行周密分析，然后给出这串宝物几百年前嵌在佛堂顶梁柱上的排列模样。给定的“月亮之眼”有N个珍珠和P根金线，所有珍珠按一定顺序有了一个序号：1、2…、N。
Input
输入数据包含一个“月亮之眼”的特征描述： 文件第一行有两个整数N和P，其中N表示宝物中的珍珠个数，P表示宝物中的金线根数； 以下P行描述珍珠连接情况： 文件第I+1行有三个整数，Ri1,Ri2,Li。其中Ri1表示第I根金线的银白色一端连接的珍珠序号；Ri2表示第I根金线的黛黑色一端连接的珍珠序号；Li表示第I根金线的长度。
Output
由于珍珠尺寸很小，所以几个珍珠可以同时镶嵌在一个位置上。 您的输出数据描述的是“月亮之眼”各个珍珠在顶梁柱上的位置，输出文件共N行： 第I行，一个整数S，它表示标号为I的珍珠在顶梁柱上距离最高位置珍珠的距离。 注意：若无解则输出仅一行，包含一个整数“-1”。
Sample Input
9 9 1 2 3 2 3 5 2 7 1 4 5 4 5 6 1 5 9 1 6 7 1 7 8 3 9 8 4
Sample Output
2 5 10 0 4 5 6 9 5
HINT
看得是http://blog.csdn.net/kongming_acm/article/details/5741538朋友的代码这里附上我的理解
#include<iostream>using namespace std;int x[501],y[501],l[501],v[501],h[501],n,p,flag=0;void dfs(int k){ int i,hh,o; if (flag)return; v[k]=1;//标记第k个为读取过的 for(i=1;i<=p;i++)//循环看有没有头是k或尾是k if ((x[i]==k)||(y[i]==k)) { o=x[i]+y[i]-k;//顺便算出另一个 hh=(x[i]==k?h[k]+l[i]:h[k]-l[i]);//算高度 if ((v[o])&&(h[o]!=hh))//如果另一个点已经特么被标记了，就说明有圈，如果h[o]也不对劲那就是见鬼了 { flag=1;return; } h[o]=hh;算出另一个点的高度 if(!v[o])dfs(o);递归 }}int main(){ cin>>n>>p; int i,min=0; for(i=1;i<=p;i++) cin>>x[i]>>y[i]>>l[i]; h[1]=0; dfs(1);//从第一个开始看 if (flag) cout<<-1<<endl; else{ for(i=1;i<=n;i++) if(h[i]<min) min=h[i]; for(i=1;i<=n;i++) cout<<h[i]-min<<endl; } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。