中心台站建设

成绩 0 开启时间 2013年01月16日 星期三 09:15
折扣 0.8 折扣时间 2013年01月16日 星期三 09:15
允许迟交 是 关闭时间 2013年01月16日 星期三 09:15
输入文件 zpj.in 输出文件 zpj.out
【问题描述】
    n个城市之间有通讯网络，从这n个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻，同时为降低造价，要使中心台站数目最少。
【输入格式】
输入文件有若干行
第一行，一个整数n，表示共有n个城市(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无直接通讯线路。数字为1表示有，0表示无。
【输出格式】
输出文件有若干行
第一行，1个整数a，表示最少中心台站数目。
第二行一个整数b,表示共有b种方案。下面有b行，每行有a个整数，表示一种建站方案。多种方案输出时，输出顺序按城镇编号由小到大字典序输出。
【输入输出样例】
输入文件名： zpj.in

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

输出文件名：zpj.out

2

5

1 5

1 6

2 5

3 4

4 5