内存优化版（100分）：
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 using namespace std; 4 const int N=19; 5 __int64 dp[1<<N][N],ans;int n,m,st; 6 bool map[N][N],mp[N]; 7 void read() 8 { 9 scanf("%d%d",&n,&m); 10 for(int i=1,a,b;i<=m;i++) 11 { 12 scanf("%d%d",&a,&b); 13 a-=2;b-=2; 14 if(a<0) mp[b]=true;//与-1号点连接的点 15 else if(b<0) mp[a]=true; 16 else map[a][b]=map[b][a]=true; 17 } 18 n--; 19 } 20 void special() 21 { 22 //预先算出包含第一个点(称这个点为-1号点)的方案，节约空间 23 for(int i=0;i<n;i++) 24 if(mp[i]) dp[1<<i][i]=1; 25 for(int i=0;i<(1<<n);i++) 26 for(int j=0;j<n;j++)//枚举终点 27 { 28 if(!dp[i][j]) continue;//要求存在dp[i][j] 29 if((i&(1<<j))) //要求i包含j点 ,j是结尾 30 { 31 if(mp[j]&&i-(1<<j)>0)//-1和j有边 ,>=3条边 32 ans+=dp[i][j]; 33 for(int k=0;k<n;k++)//拓展链 34 if((!(i&(1<<k)))&&map[k][j])//k不在i中 ,k,j有边 35 dp[i|(1<<k)][k]+=dp[i][j]; 36 } 37 } 38 } 39 void go() 40 { 41 for(int i=0;i<(1<<n);i++) 42 for(int j=0;j<n;j++) 43 dp[i][j]=0; 44 for(int i=0;i<n;i++) dp[1<<i][i]=1; 45 for(int i=0;i<(1<<n);i++) 46 { 47 for(int j=0;j<n;j++)//结尾 48 { 49 if(!dp[i][j]) continue; 50 st=-1;//标志是否找到最小起点 51 for(int k=0;k<n;k++)//最小开头 52 { 53 if(i&(1<<k)) 54 { 55 st=k; 56 if(map[j][k]&&i>(1<<k)+(1<<j))//j,k相连，>=3条边 57 ans+=dp[i][j]; 58 break; 59 } 60 } 61 if(st!=-1) 62 { 63 for(int k=st+1;k<n;k++) 64 { 65 if(!(i&(1<<k))&&map[k][j])//不在i中，且和结尾有边 66 { 67 dp[i|(1<<k)][k]+=dp[i][j]; 68 } 69 } 70 } 71 } 72 } 73 printf("%I64d",ans>>1); //顺时针逆时针有重复 74 } 75 int main() 76 { 77 read(); 78 special(); 79 go(); 80 system("pause"); 81 return 0; 82 }
MLE版（long long改成__int64可以得到90分）:
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 using namespace std; 4 const int N=20; 5 long long dp[1<<N][N],ans;int n,m,st; 6 bool map[N][N]; 7 void read() 8 { 9 scanf("%d%d",&n,&m); 10 for(int i=1,a,b;i<=m;i++) 11 { 12 scanf("%d%d",&a,&b); 13 a--;b--; 14 map[a][b]=map[b][a]=true; 15 } 16 } 17 void go() 18 { 19 for(int i=0;i<n;i++) dp[1<<i][i]=1; 20 for(int i=0;i<(1<<n);i++) 21 { 22 //printf("%lld\n",i); 23 for(int j=0;j<n;j++)//结尾 24 { 25 if(!dp[i][j]) continue; 26 st=-1; 27 for(int k=0;k<n;k++)//最小开头 28 { 29 if(i&(1<<k)) 30 { 31 st=k; 32 if(map[j][k]&&i>(1<<k)+(1<<j)) 33 { 34 ans+=dp[i][j]; 35 } 36 break; 37 } 38 } 39 if(st!=-1) 40 { 41 for(int k=st+1;k<n;k++) 42 { 43 if(!(i&(1<<k))&&map[k][j])//不在i中，且和结尾有边 44 { 45 dp[i|(1<<k)][k]+=dp[i][j]; 46 } 47 } 48 } 49 } 50 } 51 printf("%lld\n",ans>>1); 52 } 53 int main() 54 { 55 read(); 56 go(); 57 system("pause"); 58 return 0; 59 }