记录编号	91904	评测结果	AAAAAAAAAA
题目名称	中心台站建设	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-03-17 13:30:07	内存使用	1.41 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=110;
int N;
int c[SIZEN][SIZEN]={0};
bool plan[10000][SIZEN]={0};//方案
int cnum=SIZEN,pnum=0;//中心台站的最少数量,方案数目
bool nowp[SIZEN]={0};
bool same(bool *a,bool *b){
	for(int i=1;i<=N;i++) if(a[i]!=b[i]) return false;
	return true;
}
void DFS(int x,int now){
	if(now>cnum) return;
	if(x==N+1){
		if(now<cnum) cnum=now,pnum=0;
		for(int i=1;i<=pnum;i++){
			if(same(nowp,plan[i])) return;
		}
		memcpy(plan[++pnum],nowp,N+1);
		return;
	}
	for(int i=1;i<=N;i++){//x一定被某个点盖住
		if(c[x][i]){
			if(nowp[i]) DFS(x+1,now);//它已经被盖住了
			else{//它被这个点盖住,这里已经包含了选中它自身的情况
				nowp[i]=1;
				DFS(x+1,now+1);
				nowp[i]=0;
			}
		}
	}
}
void answer(void){
	printf("%d\n%d\n",cnum,pnum);
	for(int i=1;i<=pnum;i++){
		for(int j=1;j<=N;j++){
			if(plan[i][j]) printf("%d ",j);
		}
		printf("\n");
	}
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) scanf("%d",&c[i][j]);
		c[i][i]=1;
	}
}
int main(){
	freopen("zpj.in","r",stdin);
	freopen("zpj.out","w",stdout);
	read();
	DFS(1,0);
	answer();
	return 0;
}