Я пытался эта проблема SPOJ.
Проблема:
AMR10J - Смешивание химикатов
В каждой из N бутылок содержится разное химическое вещество.Для каждого химического вещества i вы определили C [i], что означает, что смешивание химических веществ i и C [i] вызывает взрыв.У вас есть K различных ящиков.Сколько способов вы можете разделить химикаты N на эти коробки так, чтобы никакие два химических вещества в одной коробке не могли вызвать взрыв вместе?
INPUT
Первая строка ввода - это число тестов T. За каждым из T тестовых наборов следует 2 строки.Первая строка каждого тестового примера содержит 2 целых числа N и K. Вторая строка каждого тестового примера содержит N целых чисел, i-е целое число, обозначающее значение C [i].Химические вещества пронумерованы от 0 до N-1.
ВЫХОД
Для каждого теста выведите число способов по модулю 1 000 000 007.
ОГРАНИЧЕНИЯ
T <= 50 </p>
2 <= N <= 100 </p>
2 <= K <= 1000 </p>
0<= C [i] <N </p>
Для всех i, i! = C [i]
ОБРАЗЕЦ ВХОДА
3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0
ВЫБОР ВЫБОРА
6
12
0
ОБЪЯСНЕНИЕ В первом тестовом случае мы не можем смешивать любые 2 химиката.Следовательно, каждая из 3 коробок должна содержать 1 химикат, что в итоге приводит к 6 путям.В третьем тестовом примере мы не можем поместить 3 химиката в 2 коробки, удовлетворяющие всем 3 условиям.
Краткое изложение проблемы, учитывая набор химикатов и набор коробок, подсчитайте, сколько возможных способовпоместить эти химикаты в коробки так, чтобы химические вещества не взорвались.Сначала я использовал метод грубой силы, чтобы решить проблему, я рекурсивно помещал химикаты в ящики и подсчитывал допустимые конфигурации, я получил TLE с первой попытки.
Позже я узнал, что проблему можно решить с помощью раскраски графа.Я могу представить химические вещества как вершины, и между химическими веществами есть грань, если они не могут быть помещены друг в друга.И набор ячеек можно использовать как цвета вершин, все, что мне нужно сделать, это подсчитать, сколько разных допустимых раскрасок графа.Я применил эту концепцию для решения проблемы, к сожалению, я снова получил TLE.Я не знаю, как улучшить свой код, мне нужна помощь.
код:
#include <bits/stdc++.h>
#define MAXN 100
using namespace std;
const int mod = (int) 1e9 + 7;
int n;
int k;
int ways;
void greedy_coloring(vector<int> adj[], int color[])
{
int u = 0;
for (; u < n; ++u)
if (color[u] == -1)//found first uncolored vertex
break;
if (u == n)//no uncolored vertexex means all vertexes are colored
{
ways = (ways + 1) % mod;
return;
}
bool available[k];
memset(available, true, sizeof(available));
for (int v : adj[u])
if (color[v] != -1)//if the adjacent vertex colored, make its color unavailable
available[color[v]] = false;
for (int c = 0; c < k; ++c)
if (available[c])
{
color[u] = c;
greedy_coloring(adj, color);
color[u] = -1;//don't forgot to reset the color
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while (T--)
{
cin >> n >> k;
vector<int> adj[n];
int c[n];
for (int i = 0; i < n; ++i)
{
cin >> c[i];
adj[i].push_back(c[i]);
adj[c[i]].push_back(i);
}
ways = 0;
int color[n];
memset(color, -1, sizeof(color));
greedy_coloring(adj, color);
cout << ways << "\n";
}
return 0;
}