题目名称 10. 信号无错传输
输入输出 dlj.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2008-03-10
开放分组 全部用户
提交状态
分类标签
图论 最值子图 搜索法
通过:54, 提交:178, 通过率:30.34%
Gravatar沉迷学习的假的Keller 100 0.000 s C++
Gravatar521 100 0.000 s C++
Gravatar梦那边的美好ET 100 0.000 s C++
Gravatarrewine 100 0.003 s C++
Gravatar雾茗 100 0.003 s C++
Gravatarytrytr 100 0.003 s C++
GravatarZXCVBNM_1 100 0.003 s C++
Gravatarztx 100 0.004 s C++
GravatarNewBee 100 0.004 s C++
GravatarGo灬Fire 100 0.004 s C++
关于 信号无错传输 的讨论
好坑的优化
Gravatar天一阁
2014-09-19 17:17 1楼
这题没有那么复杂……我一开始以为是求割顶+搜索…然并卵。
不需要优化……裸搜过了
GravatarRapiz
2016-04-14 19:02 2楼
醉了。。。
一上来写二分答案+dfs结果超时2个WA1个
索性把二分答案去了,结果就A了。。。
谁能告诉我为什么?明明剪枝一样多(而且二分答案剪枝减得更多一点点),为什么??!!
Gravatar_Itachi
2016-09-08 15:21 3楼
手残把dlj打成了dij,全E,还调了将近一整天,,,
GravatarTabing010102
2016-10-25 16:23 4楼

10. 信号无错传输

★★☆   输入文件:dlj.in   输出文件:dlj.out   简单对比
时间限制:1 s   内存限制:128 MB
【问题描述】
为提高传递信息的保密性和可靠性,两个军事基地用几套专用编码传输信号。传递信号过程中,发现某些编码在传递过程中容易混淆,影响了信息传输质量。请你在已有的编码中进行精简,既要保证传输过程中不发生混淆,又要尽量使编码集中可用编码尽量多,请你给出新的编码设计方案。
【输入格式】
输入文件有若干行
第一行,一个整数n,表示该编码规则共有n种信号(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示信号p与信号q之间是否可能混淆。数字为1表示有可能混淆,0表示不会混淆。
【输出格式】
输出文件有若干行
第一行,一个整数a,表示精简后的编码规则中有a个信号。
第二行,一个整数b,表示最佳精简方案有b种。
第3--b+2行,每行b个整数,表示一种精简方案。多种方案输出时,输出顺序按信号编号由小到大字典序输出。
【输入文件】
6
0 1 1 1 0 0
1 0 0 1 0 0
1 0 0 1 0 0
1 1 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
【输出文件】
3
2
2 3 5
2 3 6