题解 P2819 【图的m着色问题】
Creeper_LKF
2019-08-02 17:53:50
关于此题的dfs的一个优化思想。
首先说明这份代码并不是rank1，因为rank1的代码在一年前交的，好像只有两个点有时间，再是该代码经过微小的优化之后可以飞起来（但是因为个人的历史问题，我并不打算做任何这些优化）。
考虑现在染色到了第i个点，我打算染第j种颜色。
如果我发现j颜色在之前从未被染过色，而现在场上还有x种以前从未染过色的颜色。那么一旦点i染j色是局部合法的，那么我可以认为在一种全局合法的方案下染j色和其他从未出现过的颜色是等价的，于是方案数直接乘以x返回即可。
在初次写代码的时候可以想到对于第一个染色的点一定满足这个条件，于是第一个点不用搜索而直接在方案数上乘以颜色个数。然后推广一下就可以对所有点都做类似优化。
同一种代码优化级别和此题数据规模下该方法可以优化3倍时间左右。
```cpp
#include <cstdio>
using namespace std;
int n, m, k;
int col[101], tim[101], ali; // 某点的颜色，某颜色的出现次数，从未出现过的颜色数
int tabl[101][101], siz[101]; // 也是邻接表
bool has[101][101]; // 邻接表
inline void add_edge(int u, int v){
tabl[u][++ siz[u]] = v;
tabl[v][++ siz[v]] = u;
}
int dfs(int pt){
if(pt == 0) return 1;
else {
int ret = 0, tmp = 0;
for(int i = 1; i <= k; i++){
if(tim[i] == 0){ // 第一次出现
if(tmp) continue;
col[pt] = i, tim[i] ++, tmp = ali, ali --;
ret += dfs(pt - 1) * tmp;
tim[i] --, ali ++;
} else { // 非第一次出现
if(tim[i] == 0) continue;
bool flg = true;
for(int j = siz[pt]; flg && j; j--){
if(i == col[tabl[pt][j]])
flg = false;
}
if(flg) col[pt] = i, tim[i] ++, ret += dfs(pt - 1), tim[i] --;
}
}
col[pt] = 0;
return ret;
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
has[u][v] = has[v][u] = 1;
}
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if(has[i][j])
add_edge(i, j);
ali = k;
printf("%d\n", dfs(n));
return 0;
}
```