首页 > 试题广场 >

神秘代号

[编程题]神秘代号
  • 热度指数：18 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一个古老的帝国，这个帝国有 n 个城邦，这些城邦由恰好 n 条道路连结（每条路连结两个不同的城邦，保证任意两条道路连结的城邦组不同，即没有重边），所有城邦保证连通。
每个城邦有一个神秘的代号 x_i ，每个 x_i 都是一个 [0,p-1] 范围内的非负整数，其中 p 为一个已知的质数。
由于年代过于久远，这些 x_i 已经不为人知了，但是作为一个历史爱好者，你希望考证一下这些 x_i 的值。
幸运的是，你找到了一些线索，对于每条道路你都得到了一个方程，这个方程的形式为：设这条道路连结的两个城邦为 u , v ，以及有三个参数 a , b , c，那么有 a*x_u + b*x_v = c (mod p)，即这是一个在模质数 p 域下的方程。
现在你需要根据这些线索来求出一组满足条件的 x_i ，数据保证有解且解唯一。

输入描述:
第一行两个正整数 n , p ( 3 ≤ n ≤ 10^5 , 3 ≤ p ≤ 10^9 )。
接下来 n 行，每行五个整数 u , v , a , b , c 描述一条道路及其参数 ( 1 ≤ u,v ≤ n , 1 ≤ a,b < p , 0 ≤ c < p )。


输出描述:
输出 n 行，依次为 x_i (0 ≤ x_i < p)。
示例1

输入

6 5
1 4 3 1 0
4 3 1 3 2
4 2 1 3 4
2 6 1 1 2
3 5 1 2 3
2 3 3 4 0

输出

0
3
4
0
2
4
算法知识视频讲解
添加回答
hades496头像 hades496
相当于n个方程，n个未知数，解方程组：
1、n个点n条边，必定存在一个环，所以先找出这个环
2、然后联立环上的所有方程，解出任意一个节点i的值x
3、从i出发，遍历整个图，因为i的值x已知，可以直接根据一条边解出另一端的节点值，依次类推可以求得所有节点的值
整个过程就是把图遍历3遍over.
发表于 2017-07-21 10:20:27 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 基环树 美团 测试开发工程师 大数据开发工程师 树 Java工程师
来自：CodeM 2017美...
难度：
1条回答 2569浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号