AOJ 894.种花

161


题目



点击显/隐题目

Description
花老师有一个农场,农场的花一共有 4 种颜色, 花老师不喜欢老旧的东西,所以,她希望每天种花的方案都不一样。特别地,她也觉得两种一样颜色的花种在相邻的位置会很无聊。现在,她想知道,一共有多少种花的方案。这里要注意的是,农场的种花的位置是不规则的。因此我们给出一对一对的相邻的位置的关系。


第一行两个数 N 和 M,表示种花的位置的个数和相邻的位置的对数
接下来 M 行,每行一组数 A, B 表示 A, B 相邻


一个数表示染色方法数


5 4
1 2
1 3
1 4
1 5


324




题解



直接暴力跑就行
枚举所有的情况(使用递归),判断能否涂上特定的颜色,如果能成功枚举到终点就计数
不需要想太复杂

代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 15;
const int maxm = 55;

bool Edge[maxn][maxn];
int color[maxn];
int n, m;
int sum;

bool judge(int t, int c) {
    for (int i = 1; i <= n; i++) {
        if (Edge[t][i]) {      //相邻
            if (color[i] == c) //有重复的颜色
                return false;
        }
    }
    return true;
}

//给t涂上c
void dfs(int t, int c, int deep) {
    if (!judge(t, c))
        return;

    // for (int i = 0; i < deep; i++)
    //     cout << "\t";
    // cout << "fill " << t << " in color " << c << endl;

    color[t] = c;

    if (t < n)
        for (int k = 1; k <= 4; k++)
            dfs(t + 1, k, deep + 1);
    else
        sum++;

    color[t] = 0;
}

//从 s 开始给连通分量内的点涂色
int begin(int s) {
    sum = 0;
    for (int k = 1; k <= 4; k++) {
        dfs(s, k, 0);
    }

    //cout << s << "  " << sum << endl;

    return sum;
}

int main() {
#ifdef debug
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int START = clock();
#endif
    cin.tie(0);
    cin.sync_with_stdio(false);

    while (cin >> n >> m) {
        memset(Edge, false, sizeof(Edge));

        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            Edge[a][b] = Edge[b][a] = true;
        }

        int ans = begin(1);

/*
        for (int i = 2; i <= n; i++) {
            if (color[i] == 0) {
                ans *= begin(i);
            }
        }
*/
        cout << ans << endl;
    }

#ifdef debug
    printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论