| 题目名称 | 9. 中心台站建设 |
|---|---|
| 输入输出 | zpj.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 11 |
| 题目来源 |
 cqw
于2008-03-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：88， 提交：273， 通过率：32.23% | ||||
 dateri |
100 | 0.000 s | 0.00 MiB | C++ |
 1020 |
100 | 0.000 s | 0.00 MiB | C++ |
 惠惠 |
100 | 0.002 s | 0.90 MiB | C++ |
 ONCE AGAIN |
100 | 0.002 s | 1.22 MiB | C++ |
 cuixiaofei |
100 | 0.003 s | 0.19 MiB | Pascal |
 Pine |
100 | 0.003 s | 1.30 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.004 s | 1.41 MiB | C++ |
 Youngsc |
100 | 0.004 s | 38.88 MiB | C++ |
 FoolMike |
100 | 0.005 s | 0.33 MiB | C++ |
 guosl |
100 | 0.005 s | 0.34 MiB | C++ |
| 本题关联比赛 | |||
| 练习222 | |||
| 练习222 | |||
| EYOI与SBOI开学欢乐赛7th | |||
| 关于 中心台站建设 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
本蒟蒻不会大佬的高级优化，只会最优性剪枝+卡时
| ||||
|
回复 @皓芷 :
%%%  Hyoi_0Koto
2017-05-16 21:52
9楼
| ||||
|
| ||||
|
| ||||
|
如果样例答案是3 12 ... 注意赋值顺序，自己也能传给自己
Hzoi_Go灬Fire
2016-10-15 09:58
6楼
| ||||
|
| ||||
|
爆嗖就能过！？
 _Itachi
2016-08-12 06:27
4楼
| ||||
|
请注意搜的顺序……
 水中音
2014-12-26 15:52
3楼
| ||||
|
样例已改好
| ||||
|
样例数据有问题，下面的系数矩阵是5行6列，而根据题意应该是6行6列的。
guosl
2012-11-22 13:41
1楼
| ||||
HtBest
皓芷
cy
cstdio【题目描述】
$n$ 个城市之间有通讯网络，从这 $n$ 个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻，同时为降低造价，要使中心台站数目最少。
【输入格式】
输入文件有若干行:
第一行，一个整数 $n$，表示共有 $n$ 个城市$(2 \leq n \leq 100)$
下面有 $n$ 行,每行有 $n$ 个数字。第 $p$ 行第 $q$ 列的数字表示城镇 $p$ 与城镇 $q$ 之间有无直接通讯线路。数字为 $1$ 表示有，$0$ 表示无。
【输出格式】
输出文件有若干行:
第一行，$1$个整数 $a$，表示最少中心台站数目。
第二行一个整数 $b$,表示共有 $b$ 种方案。下面有 $b$ 行，每行有 $a$ 个整数，表示一种建站方案。多种方案输出时，输出顺序按城镇编号由小到大字典序输出。
【样例输入1】
6 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0
【样例输出1】
2 5 1 5 1 6 2 5 3 4 4 5
【样例输入/输出2】
样例2