AT_abc199_d题解

suzhikz · 2023-10-20 23:04:55 · 题解

前言：

这题是学校模拟赛出的题，开始的时候没有头绪，后来在讲评之后也是恍然大悟了。临近 noip，写篇题解希望 rp++，预祝大家考的都会。

思路：

这题一看数据量就知道肯定是爆搜或者状压了，但是显然不满足无后效性（还是我太蒻了？），所以直接写爆搜。将图分为几个连通互相没有边的图，分开处理，最后答案相乘即可。

易错

爆搜相信大家都会，我在下面写一些易错点：

1. 这个图不一定是树，当图中有环时，需要标记，否则答案就会加两遍（or 更多），样例一就是这种情况。
2. 一个点的颜色需要先与父亲判断，重复就要跳过，否则计算量过大，喜提 TLE。
3. 记得开 long long，否则样例 4 就可以卡掉。

   code

   #include<iostream>
   #include<cmath>
   #include<iomanip>
   #include<cstdio>
   #include<string>
   #include<deque>
   #include<stack>
   #include<queue>
   #include<vector>
   #include<stdio.h>
   //#include<map>
   #include<string.h>
   #include<time.h>
   #include<stdlib.h>
   #include<bitset>
   using namespace std;
   int n,m;
   vector<int> w[25];//图
   long long ans[25],tot;//答案
   bool vis[25];//是否搜过
   int huan[25][25];//有没有环
   int c[25];
   int work(int x,int fa){
    int an=0;
    vis[x]=1;
    if(c[x]){//重复搜到肯定是因为有环。
        huan[x][fa]=1;//这个环肯定包括这个点和他的两个儿子，一个儿子搜过了，只需要再特判另一个即可。
        return c[x]!=c[fa];
    }
    for(int i=1;i<=3;i++){
        if(i==c[fa])continue;//易错点2。
        c[x]=i;
        int book=1;
        memset(huan[x],0,sizeof(huan[x])); //初始化也是易错。
        for(int j=0;j<w[x].size();j++){
            int v=w[x][j];
            if(!huan[x][v])book*=work(v,x);//没有环或环还没搜。
        }
        c[x]=0;
        an+=book;
    }
    return an;
   }
   int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        w[u].push_back(v);
        w[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            ans[++tot]=work(i,0);
        }
    }
    for(int i=2;i<=tot;i++)ans[i]*=ans[i-1];
    cout<<ans[tot];
    return 0;
   }