题解 P4019 【多边形染色】

AmamiyaUmi · 2017-12-23 23:42:22 · 题解

咸鱼的blog：http://www.neptuuz.com/wordpress/?p=237

经典的环形dp，枚举开头，对结尾的状态要与开头判断一下是否合法

dp[i][j]表示第i个顶点染颜色j的方案数，可以得到

dp[i][j] = ∑dp[i-1][k] (颜色j可以被染上 && i和i-1被改变边属性时：j=k；否则j != k)

复杂度O(nc^3)

然后这题坑的地方是2操作对于同一顶点有多个，也就是说对于一个顶点可能不能染多种颜色（卡了两个点不然AK了QAQ）

#include<stdio.h>
#include<iostream>
#include<string.h>
#define MAXN 50010
#define MOD 987654321
using namespace std;

int n, m, c, uncol[MAXN][15], e[MAXN], dp[MAXN][15], ans;

int main() {
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1, opt, x, y; i <= m; ++i) {
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) {
            for (int j = 1; j <= c; ++j) {
                if (j != y) uncol[x][j] = 1;
            }
        } else if (opt == 2) {
            uncol[x][y] = 1;
        } else {
            if (x > y) swap(x, y);
            e[y] = x;
        }
    }
    for (int p = 1; p <= c; ++p) {
        if (uncol[1][p]) continue;
        memset(dp, 0, sizeof(dp));
        dp[1][p] = 1;
        for (int i = 2; i < n; ++i) {
            for (int j = 1; j <= c; ++j) {
                if (uncol[i][j]) continue;
                if (e[i]) {
                    dp[i][j] += dp[i-1][j];
                    dp[i][j] %= MOD;
                } else for (int k = 1; k <= c; ++k) {
                    if (j == k) continue;
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= MOD;
                }
            }
        }
        for (int i = 1; i <= c; ++i) {
            if (uncol[n][i] || i == p) continue;
            if (e[n]) {
                dp[n][i] += dp[n-1][i];
                dp[n][i] %= MOD;
            } else for (int j = 1; j <= c; ++j) {
                if (i == j) continue;
                dp[n][i] += dp[n-1][j];
                dp[n][i] %= MOD;
            }
        }
        for (int i = 1; i <= c; ++i) {
            ans += dp[n][i];
            ans %= MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}```