中心台站建设

Grade 0 Open Time Wednesday, 16 January 2013, 9:15 am
Discount 0.8 Time Discount Wednesday, 16 January 2013, 9:15 am
Allow late Yes Close Time Wednesday, 16 January 2013, 9:15 am
Input file zpj.in Output file 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