感觉最近做题都做傻了，这道题居然没有任何思路，（去世摸鱼中）

 

 

 

种植花圃

题目描述

众所周知，蔡老板有一个巨大的庄园。蔡老板已经厌倦了庄园现有的花圃颜色，决定重新对庄园重新种植花圃。为了简化这个问题，我们把蔡老板的庄园抽象成了一个无向连通图 GG 。他的每一块花圃被抽象成了图中的一个顶点，相邻的花圃所表示的结点之间有连边。

蔡老板一共采购了 mm 种不同的颜色的花。他要用这些颜色的花为他的庄园换色，而且每一个花圃有且只能有一种颜色的花。即图中每个顶点只能着一种颜色。

如果有一种种植的方案使得蔡老板的庄园中相邻的花圃着不同颜色，则称这个庄园是 mm 可着色的。蔡老板现在想找出所有不同的着色法。

输入

第 11 行有 33 个正整数 nn ， kk 和 mm ，表示给定的图 GG 有 nn 个顶点和 kk 条边， mm 种颜色。顶点编号为 11 ， 22 ， ⋯⋯ ，nn 。

接下来的 kk 行中，每行有 22 个正整数 uu , vv ，表示图 GG 的一条边 (u,v)(u,v) 。

输出

输出包含一个整数，表示计算出的不同的着色方案数输出。

样例

输入

5 8 41 21 31 42 32 42 53 44 5

输出

48

限制与约定

对于所有数据 n≤100n≤100 , k≤2500k≤2500 , m≤5m≤5

时间限制：1 s

空间限制：128 MB

 

 

 

因为数据很小，所以直接模拟染色就行了，说实话这可能还不算是一道树上染色问题（题目打脸）；

dfs搞定

#include
      
       #include
       
        #include
        
         using namespace std;int n,k,m;int g[3000][3000];int col[3000];int ans,flag;void dfs(int x){    if(x==n+1)    {        ans++;        return ;    }    for(int i=1;i<=m;i++)    {        flag=0;        for(int j=1;j<=n;j++)        {            if(g[x][j]&&col[j]==i)            {                flag=1;                break;            }        }        if(flag==1) continue;        col[x]=i;        dfs(x+1);        col[x]=0;    }}int main(){    scanf("%d%d%d",&n,&k,&m);    for(int i=1;i<=k;i++)    {        int x,y;        scanf("%d%d",&x,&y);        g[x][y]=1;        g[y][x]=1;    }    dfs(1);    printf("%d",ans);    return 0;}