中心台站建设
时间限制：1 s 内存限制：128 MB 【问题描述】 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
最小支配集
为了方便，我们先对每个点建自环。 那么。对于每个点u，一定有一条或多条(u,v) 满足点v是建基站的。 我们可以从小到大枚举v是否有基站。 函数原型和之前一样。void dfs(int u,int now) 1. 如果v本来就有基站，那么 dfs(u+1,now) 搜索下一个点。 2. 如果v没有基站，我们设置基站，那么 dfs(u+1,now+1) 搜索一下个点。
剪枝
最优性剪枝：和之前一样。 排除等效冗余：我们枚举时，只需要枚举某个还没建基站的点，和任意一个建基站的点进行搜索。 这个思路可以保证调用dfs(u,now)时， 1..(u-1)全部都满足约束条件。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXV=100+1,MOD=1000003; int n,minn=1000,ans; bool e[MAXV][MAXV],pkd[MAXV],ht[MOD]; char buf[20000],tmp[2000]; bool try_insert(){ unsigned int hv=0,fac=1; for(int i=1;i<=n;i++,fac*=2,fac%=MOD) if(pkd[i]) hv+=fac,hv%=MOD; if(ht[hv]) return false; else return ht[hv]=1; } void dfs(int u=1,int now=0){//考虑点u，目前已经建了now个基站 if(now>minn) return; else 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); cin>>n; for(int i=1;i<=n;e[i][i]=1,i++) for(int j=1;j<=n;j++) cin>>e[i][j]; dfs(); cout<<minn<<endl<<ans<<endl<<buf; }为了方便，我们先对每个点建自环。 那么。对于每个点 u，一定有一条或多条 (u,v) 满足点 v 是建基站的。 我们可以从小到大枚举 v 是否有基站。 函数原型和之前一样。void dfs(int u,int now) 1. 如果 v 本来就有基站，那么 dfs(u+1,now) 搜索下一个点。 2. 如果 v 没有基站，我们设置基站，那么 dfs(u+1,now+1) 搜索一下个点。
剪枝
最优性剪枝：和之前一样。 排除等效冗余：我们枚举时，只需要枚举某个还没建基站的点，和任意一个建基站的点进行搜索。
其他
思路1是盲目的枚举，直到最后一步才判断是否可行。 而这个思路可以保证调用dfs(u,now)时，1…(u-1) 全部都满足约束条件。
ps:
//此题为图论中的最小支配集 #include <cstdio> #include <bitset> #include <vector> #include <algorithm> using namespace std; struct stVs { vector<int> Vs; bool operator<(const stVs &x) const { for (int i=0;i<(int)Vs.size();++i) { if(Vs[i]!=x.Vs[i]) return (Vs[i]<x.Vs[i]); } return false; } }; int nN; int a[100][100]; vector<bitset<100> > vVs[100]; vector<stVs> uVs; int main(void) { freopen("zpj.in","r",stdin); freopen("zpj.out","w",stdout); scanf("%d",&nN); for (int i=0;i<nN;++i) { for (int j=0;j<nN;++j) { int nTemp; scanf("%d",&nTemp); a[i][j]=nTemp; if(nTemp==1) { bitset<100> bsTemp; bsTemp.set(j); vVs[i].push_back(bsTemp); } } bitset<100> bsTemp; bsTemp.set(i); vVs[i].push_back(bsTemp); } { vector<int> V; for (int i=0;i<nN;++i) { if((int)vVs[i].size()==nN) { V.push_back(i+1); } } if(V.size()>0) { printf("1\n"); printf("%d\n",(int)V.size()); sort(V.begin(),V.end()); for (int i=0;i<(int)V.size();++i) { printf("%d\n",V[i]); } fclose(stdin); fclose(stdout); return 0; } } vector<bitset<100> > bsTemp,bsTemp1; bsTemp=vVs[0]; for (int k=1;k<nN;++k) { for (int i=0;i<(int)bsTemp.size();++i) { bitset<100> bs1=bsTemp[i]; for (int j=0;j<(int)vVs[k].size();++j) { bitset<100> bs2=vVs[k][j]; bs2 |= bs1; bsTemp1.push_back(bs2); } } bool bFind=true; while(bFind) { bFind=false; for (int i=0;i<(int)bsTemp1.size();++i) { bitset<100> bs=bsTemp1[i]; vector<bitset<100> >::iterator itr; int j=0; for (itr=bsTemp1.begin();itr!=bsTemp1.end();++itr,++j) { if(i==j) continue; bitset<100> bs1=*itr; bs1 &= bs; if(bs == bs1) { bsTemp1.erase(itr); bFind=true; break; } } if(bFind) break; } } bsTemp=bsTemp1; bsTemp1.clear(); } int nCount=nN; for (int i=0;i<(int)bsTemp.size();++i) nCount=min(nCount,(int)bsTemp[i].count()); printf("%d\n",nCount); vector<int> vResults; for (int i=0;i<(int)bsTemp.size();++i) { if(bsTemp[i].count()==nCount) vResults.push_back(i); } printf("%d\n",(int)vResults.size()); for (int i=0;i<(int)vResults.size();++i) { vector<int> vTemp; for (int j=0;j<nN;++j) { if(bsTemp[vResults[i]].test(j)) vTemp.push_back(j+1); } sort(vTemp.begin(),vTemp.end()); stVs stTemp; stTemp.Vs=vTemp; uVs.push_back(stTemp); } sort(uVs.begin(),uVs.end()); for (int i=0;i<(int)uVs.size();++i) { for (int j=0;j<(int)uVs[i].Vs.size();++j) printf("%d ",uVs[i].Vs[j]); printf("\n"); } fclose(stdin); fclose(stdout); return 0; }