我们直接状压表示最小值，然后我们状态里面枚举最后一个点所在的相同颜色的集合，复杂度为3^17=10^8。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef unsigned un; const int maxn=1<<18; un uo[maxn]; un mm(un n,int m){ un s=1; un k=n; while(m){ if(m&1){ s=s*k; } k=k*k; m>>=1; } return s; } void init(){ for(int i=0;i<maxn;i++){ uo[i]=mm(233,i); } } bool is[maxn]; int a[20]; char c[100]; un dp[maxn]; int main() { int t; int n; init(); cin>>t; while(t--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",c); a[i]=0; for(int j=n-1;j>=0;j--){ a[i]=a[i]<<1; a[i]|=c[j]-'0'; } } int p=1<<n; dp[0]=0; for(int i=1;i<p;i++){ int flag=1; for(int j=0;j<n;j++){ if((i>>j)&1){ if(i&(a[j])){ flag=0; break; } } } is[i]=flag; } un ans=0; for(int i=1;i<p;i++){ int w=i&(-i); dp[i]=dp[i^w]+1; int q=i^w; for(int j=q;j;j=(j-1)&q){ if(is[w|j]) dp[i]=min(dp[i],dp[i^(w|j)]+1); } ans+=dp[i]*uo[i]; } printf("%u\n",ans); } }