个人中心
gpt4 book ai didi

图的 m 着色问题

转载 作者：知者 更新时间：2024-03-12 00:45:11 27 4
gpt4 key购买 nike

一 问题描述

二 算法说明

本问题为图的 m 着色问题，可采用回溯法（m 叉树）解决。

三 代码

package com.platform.modules.alg.alglib.p2819;

public class P2819 {
    public String output = "";
    private int n, m;
    private int a = 1, b = 1;
    int sum = 0;
    int graph[][] = new int[20][20];
    int color[] = new int[20];

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[2]);
        for (int i = 1; i < line.length; i++) {
            String[] connection = line[i].split(" ");
            graph[Integer.parseInt(connection[0])][Integer.parseInt(connection[1])] = 1;
            graph[Integer.parseInt(connection[1])][Integer.parseInt(connection[0])] = 1;
        }
        backtrack(1);
        output += sum;
        return output;
    }

    boolean ok(int c) {
        for (int k = 1; k <= n; k++) {
            if (graph[c][k] == 1 && color[c] == color[k]) {
                return false;
            }
        }
        return true;
    }

    void backtrack(int cur) {
        if (cur > n) {
            sum++;
        } else {
            for (int i = 1; i <= m; i++) {
                color[cur] = i;
                if (ok(cur)) {
                    backtrack(cur + 1);
                }
                color[cur] = 0;
            }
        }
    }
}

四 测试

27 4 0
文章推荐： 七夕专属博文-使用QGraphics画“红心“或“黑心“（含数学模型讲解）
文章推荐： 算法平台可视化 TOJ3374
文章推荐： 生日蛋糕问题
文章推荐： 用平衡二叉搜索树解决硬木种类问题
知者
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com