9. 中心台站建设
★★☆ 输入文件：zpj.in 输出文件：zpj.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
n个城市之间有通讯网络，从这n个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻，同时为降低造价，要使中心台站数目最少。
【输入格式】
输入文件有若干行
第一行，一个整数n，表示共有n个城市(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无直接通讯线路。数字为1表示有，0表示无。
第一行，一个整数n，表示共有n个城市(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无直接通讯线路。数字为1表示有，0表示无。
【输出格式】
输出文件有若干行
第一行，1个整数a，表示最少中心台站数目。
第一行，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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 101
#define mod 1000003
using namespace std;
int n,mn=,ans;
char buf[],tmp[];
bool e[maxn][maxn],pkd[maxn],ht[mod];
bool try_Insert(){
int hv=,fac=;
for(int i=;i<=n;i++){
if(pkd[i]){
hv+=fac;
hv%=mod;
}
fac*=;
fac%=mod;
}
if(ht[hv])return ;
else return ht[hv]=;
}
void dfs(int u,int now){
if(now>mn)return;
if(u>n){
if(now<mn)mn=now,ans=,buf[]=;
if(!try_Insert())return;
tmp[]=;
ans++;
for(int i=;i<=n;i++)
if(pkd[i])sprintf(tmp+strlen(tmp),"%d ",i);
sprintf(tmp+strlen(tmp),"\n");
strcat(buf,tmp);
}
else{
bool flag=;
for(int v=;v<=n;v++)
if(e[u][v])
if(pkd[v]){
if(!flag)flag=,dfs(u+,now);
}
else{
pkd[v]=;
dfs(u+,now+);
pkd[v]=;
}
}
}
int main(){
freopen("zpj.in","r",stdin);freopen("zpj.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
scanf("%d",&e[i][j]);
if(i==j)e[i][j]=;
}
dfs(,);
cout<<mn<<endl<<ans<<endl<<buf;
}