cogs 9. 中心台站建设。。。
9. 中心台站建设
★★☆ 输入文件：zpj.in 输出文件：zpj.out简单对比
时间限制：1 s 内存限制：128 MB
第一行，一个整数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.out2
5
1 5
1 6
2 5
3 4
4 5
思路：呵呵哒
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXV 101 #define MOD 1000003 using namespace std; int n,minn=1000,ans; char buf[20000],tmp[2000]; bool e[MAXV][MAXV],pkd[MAXV],ht[MOD]; bool try_insert(){ unsigned int hv=0,fac=1; for(int i=1;i<=n;i++){ if(pkd[i]){ hv+=fac; hv%=MOD; } fac*=2; fac%=MOD; } if(ht[hv]) return false; else return ht[hv]=1; } void dfs(int u,int now){ if(now>minn) return; //剪枝 if(u>n){ if(now<minn) minn=now,ans=0,buf[0]=0;//更新最小值。 if(!try_insert()) return; //剪枝 tmp[0]=0; ans++; for(int i=1;i<=n;i++) if(pkd[i]) sprintf(tmp+strlen(tmp),"%d ",i); sprintf(tmp+strlen(tmp),"\n"); strcat(buf,tmp); } else { bool flag=0; for(int v=1;v<=n;v++) if(e[u][v]) if(pkd[v]){ if(!flag) flag=1,dfs(u+1,now); } else{ pkd[v]=1; dfs(u+1,now+1); pkd[v]=0; } } } int main(){ freopen("zpj.in","r",stdin); freopen("zpj.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ cin>>e[i][j]; if(i==j) e[i][j]=1; } dfs(1,0); //从1号节点开始修建，已经修建了0个站台。 cout<<minn<<endl<<ans<<endl<<buf; }优质内容筛选与推荐>>
1、初识 Swagger
2、LCA(包含RMQ)
3、用户自己排序记录
4、java 判断一个字符串中的数字：是否为数字、是否包含数字、截取数字
5、Xshell SSH端口转发说明文档