【题解】 CF11D A Simple Task
发布时间:2020-12-14 05:13:44 所属栏目:大数据 来源:网络整理
导读:【题解】 CF11D A Simple Task 传送门 (n le 20) 考虑状态压缩 (dp) 。 考虑状态, (dp(i,j,O)) 表示从 (i) 到 (j) 经过点集 (O) 的路径有多少。 (dp(i,O bigcup i)=Sigma dp(i,p,O)) , (j-p) 有一条边。 考虑内存,我们可以认定状态压缩
【题解】 CF11D A Simple Task传送门 (n le 20) 考虑状态压缩(dp)。 考虑状态,(dp(i,j,O))表示从(i)到(j)经过点集(O)的路径有多少。 (dp(i,O bigcup i)=Sigma dp(i,p,O)),(j-p)有一条边。 考虑内存,我们可以认定状态压缩串中(lowbit(x))位是一条路的起点,这样我们直接省掉一维。空间限制卡进去了。 考虑答案怎么统计,就是((Sigma (dp(i,O)+dp(j,i,O))-m) div2) 然后就是神仙一般的代码,orz Van #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #include<bitset> #include<vector> #include<map> #include<ctime> #include<cstdlib> #include<set> #include<bitset> #include<stack> #include<list> #include<cmath> using namespace std; #define RP(t,a,b) for(register ll (t)=(a),edd_=(b);t<=edd_;++t) #define DRP(t,edd_=(b);t>=edd_;--t) #define ERP(t,a) for(int t=head[a];t;t=e[t].nx) #define Max(a,b) ((a)<(b)?(b):(a)) #define Min(a,b) ((a)<(b)?(a):(b)) #define TMP template<class ccf> #define lef L,R,l,mid,pos<<1 #define rgt L,mid+1,r,pos<<1|1 #define midd register int mid=(l+r)>>1 #define chek if(R<l||r<L)return #define all 1,n,1 #define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1] #define lowbit(x) ((x)&(-(x))) typedef long long ll; TMP inline ccf qr(ccf k){ char c=getchar(); ccf x=0; int q=1; while(c<48||c>57) q=c==45?-1:q,c=getchar(); while(c>=48&&c<=57) x=x*10+c-48,c=getchar(); if(q==-1) x=-x; return x; } const int maxn=20; const ll mod=1e9+7; bool e[maxn][maxn]; ll dp[maxn][1<<maxn]; ll ans; int n,m; int main(){ #ifndef ONLINE_JUDGE freopen("hamilton.in","r",stdin); freopen("hamilton.out","w",stdout); #endif n=qr(1); m=qr(1); const int maxw=(1<<n)-1;int t1,t2; RP(t,1,m){ t1=qr(1)-1; t2=qr(1)-1; e[t1][t2]=1; e[t2][t1]=1; //dp[t1][(1<<t1)|(1<<t2)]=1; //dp[t2][(1<<t1)|(1<<t2)]=1; } RP(t,n-1) dp[t][(1<<t)]=1;//lowbit(x)是一个路径的起点 RP(k,maxw){ RP(t,n-1){//起点 RP(i,n-1){//目标点 if(e[t][i]){ if(lowbit(k)>(1<<i)) continue; if((1<<i)&k){ if((1<<i)==lowbit(k)) ans+=dp[t][k]; } else dp[i][k|(1<<i)]+=dp[t][k]; } } } } printf("%lldn",((ans-m)>>1)); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |