中国地图上色问题

yyyhy · 2024-12-18 20:51:08 · 学习·文化课

中国地图上色问题

背景：数学老师上课讲了一道这样的题并说我们方法太慢了，求不了中国地图的上色问题。
question：正方体六个面上分别标有A，B，C，D，E，F六个字母，现用5种不同的颜色给此正方体六个面染色，要求有公共棱的面不能染同一种颜色，则不同的染色方案有____种。

众所周知，地图上色如何不让相邻地区同色是一个小问题。

特别地，我们认为，虽然台湾和福建、海南和广东隔了一条海峡，但是不能同色；同时注意，香港和澳门也认为不能同色。

然后求4色、5色分别有多少种上色方案。（3色是0）

暴搜代码：

#include <cstdio>
#include <algorithm>
#include <vector> 
#include <windows.h> 
#define maxn 2000
#define int long long 

int n, m, x, ans, len[maxn + 10];
std :: vector <int> S[maxn + 10];
int now[maxn + 10], used[maxn + 10][maxn + 10];

inline void dfs(int i) {
    if (i > n) {
        ans++; return;
    } 
    for (int j = 1; j <= m; j++) used[i][j] = 0;
    for (int j : S[i]) used[i][now[j]] = 1;
    for (int j = 1; j <= m; j++)
        if (!used[i][j]) {
            now[i] = j; dfs(i + 1); now[i] = 0;
        }
    return;
}

signed main(void) {
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        printf("%lld号点连接情况：", i); 
        scanf("%lld", len + i);
        for (int j = 1; j <= len[i]; j++)
            scanf("%lld", &x), S[i].push_back(x); 
    }
    if (m < 1) {
        puts("???"); return 0;
    }
    dfs(1);
    printf("%lld\n", ans);

    system("pause");
    return 0;
}

我们进行一个编号，如下（这样编号是因为每一个省都和尽可能多的已确定省相连可以减少枚举量）：
|省级行政区|编号| |:-:|:-:| |新疆|1| |青海|2| |西藏|3| |四川|4| |甘肃|5| |内蒙古|6| |宁夏|7| |陕西|8| |山西|9| |河北|10| |北京|11| |天津|12| |辽宁|13| |吉林|14| |黑龙江|15| |山东|16| |河南|17| |江苏|18| |安徽|19| |湖北|20| |重庆|21| |上海|22| |浙江|23| |江西|24| |湖南|25| |贵州|26| |云南|27| |广西|28| |福建|29| |广东|30| |台湾|31| |香港|32| |澳门|33| |海南|34|

然后求 4 色，
input：

34 4
0
1 1
2 1 2
2 2 3
3 1 2 4
1 5
2 5 6
4 4 5 6 7
2 6 8
2 6 9
1 10
2 10 11
2 6 10
2 6 13
2 6 14
1 10
4 8 9 10 16
1 16
3 16 17 18
3 8 17 19
3 4 8 20
1 18
3 18 19 22
3 19 20 23
3 20 21 24
3 4 21 25
3 3 4 26
3 25 26 27
2 23 24
4 24 25 28 29
1 29
1 30
2 30 32
1 30

\huge{answer=2163096576}

然后求 5 色，
input：

34 5
0
1 1
2 1 2
2 2 3
3 1 2 4
1 5
2 5 6
4 4 5 6 7
2 6 8
2 6 9
1 10
2 10 11
2 6 10
2 6 13
2 6 14
1 10
4 8 9 10 16
1 16
3 16 17 18
3 8 17 19
3 4 8 20
1 18
3 18 19 22
3 19 20 23
3 20 21 24
3 4 21 25
3 3 4 26
3 25 26 27
2 23 24
4 24 25 28 29
1 29
1 30
2 30 32
1 30

背景：学校机会断电，所以写了一个可以接着跑的程序，而且方案太多所以加了一点（微量）优化：
```
#include <cstdio>
#include <algorithm>
#include <vector> 
#include <windows.h> 
#define maxn 2000
#define int long long 
```

int n, m, x, ans, len[maxn + 10], a[maxn + 10]; std :: vector <int> S[maxn + 10]; int y, now[maxn + 10], used[maxn + 10][maxn + 10];

inline void dfs(int i, int deq) { if (y) return; if (i > n) { if (now[3] > 3) { y = 1; return; } if (!(ans % 2000000000)) { printf("%lld: ", ans); for (int i = 1; i <= n; i++) printf("%lld ", now[i]); putchar('\n'); } ans++; return; } for (int j = 1; j <= m; j++) used[i][j] = 0; for (int j : S[i]) used[i][now[j]] = 1; if (deq) for (int j = 1; j < a[i]; j++) if (!used[i][j]) { now[i] = j; dfs(i + 1, 1); now[i] = 0; } for (int j = a[i]; j <= m; j++) if (!used[i][j]) { now[i] = j; dfs(i + 1, deq | (j != a[i])); now[i] = 0; } return; }

signed main(void) { scanf("%lld %lld", &n, &m); for (int i = 1; i <= n; i++) { printf("%lld号节点连接情况：", i); scanf("%lld", len + i); for (int j = 1; j <= len[i]; j++) scanf("%lld", &x), S[i].push_back(x); } scanf("%lld", &ans); for (int i = 1; i <= n; i++) scanf("%lld", a + i); if (m < 1) { puts("???"); return 0; } dfs(1, 0); printf("ans=%lld\n", ans 3 4 * 5);

system("pause");
return 0;

}


~~**正在跑**~~  
目前进度：$100\%$
#
$\Large {answer}$：

首先，以 `1 2 3 1` 开头的方案数为 $25392566071296$，然后，以 `1 2 3 4` 开头的方案数为 $16948152557568$。  
而且我们知道 `1 2 3 4` 开头等价于 `1 2 3 5` 开头。  
所以 `1 2 3` 开头的方案数为 $25392566071296+2\times 16948152557568=59288871186432$。  
同时我们又知道前三位有 $5\times 4\times 3=60$ 种方案，且都和 `1 2 3` 开头等价。  
所以，  
$$\huge{answer=60\times 59288871186432
=3557332271185920}$$
#
#### 运行记录：
12·20 22:30 字典序第 $480000000001$ 小的方案：  
`1 2 3 1 3 1 2 5 2 3 2 4 5 3 4 1 4 4 5 2 3 3 2 1 5 4 2 3 5 2 1 1 3 1`  
12·21 12:30 字典序第 $1310000000001$ 小的方案：  
`1 2 3 1 3 1 4 2 5 3 1 4 4 5 4 4 1 2 3 5 4 5 1 4 1 3 5 2 2 5 4 3 4 1`  
12·21 22:30 字典序第 $2720000000001$ 小的方案：  
`1 2 3 1 3 1 5 4 5 4 1 3 5 4 5 3 2 4 1 5 2 1 5 4 1 5 2 4 1 3 4 4 5 1`  
12·22 12:30 字典序第 $3400000000001$ 小的方案：  
`1 2 3 1 3 2 1 5 1 5 4 1 1 3 4 4 2 5 3 1 4 3 2 4 5 3 5 2 1 3 3 2 4 1`  
12·22 22:30 字典序第 $4360000000001$ 小的方案：  
`1 2 3 1 3 2 5 4 1 5 3 4 4 3 4 1 3 5 2 5 2 3 4 1 3 4 5 1 2 5 3 2 3 1`  
12·23 12:30 字典序第 $5240000000001$ 小的方案：  
`1 2 3 1 3 4 1 5 1 3 4 5 1 5 1 5 2 2 4 1 4 1 3 5 2 5 2 4 4 1 3 4 5 2`  
12·23 22:30 字典序第 $6680000000001$ 小的方案：  
`1 2 3 1 3 5 1 2 1 3 2 1 2 1 3 4 5 1 2 1 3 4 5 3 2 5 2 1 2 4 4 3 5 1`  
12·24 12:30 字典序第 $7670000000001$ 小的方案：  
`1 2 3 1 3 5 2 4 1 4 2 3 3 4 3 2 3 5 1 2 5 2 4 3 4 3 4 1 2 5 4 3 4 1`  
12·24 22:30 字典序第 $8990000000001$ 小的方案：  
`1 2 3 1 4 1 2 5 2 3 4 5 5 3 5 5 4 2 3 1 2 3 5 2 5 3 5 2 3 4 4 3 5 1`  
12·25 12:30 字典序第 $9990000000001$ 小的方案：  
`1 2 3 1 4 1 3 5 2 5 2 1 3 5 4 1 4 2 3 1 4 3 4 5 3 2 4 1 3 4 1 1 2 1`  
12·25 22:30 字典序第 $11450000000001$ 小的方案：  
`1 2 3 1 4 2 1 3 4 1 4 2 4 3 5 3 5 5 1 2 5 4 2 5 3 4 5 2 4 1 3 4 5 2`  
12·26 12:30 字典序第 $12440000000001$ 小的方案：  
`1 2 3 1 4 2 3 5 3 4 2 5 5 1 4 2 1 3 5 2 4 4 2 1 3 2 5 1 3 2 4 4 5 1`  
12·26 22:30 字典序第 $13870000000001$ 小的方案：  
`1 2 3 1 4 3 1 5 2 4 3 5 5 1 4 1 3 5 4 1 3 4 1 2 5 4 5 3 4 1 2 3 4 2`  
12·27 22:30 字典序第 $15330000000001$ 小的方案：  
`1 2 3 1 4 5 1 2 3 2 5 4 3 1 2 4 5 5 2 4 5 4 3 5 1 2 4 5 2 3 1 1 2 1`  
12·28 12:30 字典序第 $16200000000001$ 小的方案：  
`1 2 3 1 4 5 2 3 2 1 5 3 2 1 4 3 5 2 1 4 2 5 3 2 5 3 4 2 5 4 1 1 2 1`  
12·28 22:30 字典序第 $17330000000001$ 小的方案：  
`1 2 3 1 5 1 2 3 5 3 4 1 4 3 4 4 1 5 3 5 2 4 1 2 1 4 5 3 4 5 3 3 4 1`  
12·29 22:30 字典序第 $18260000000001$ 小的方案：  
`1 2 3 1 5 1 3 2 5 3 2 4 4 3 2 4 1 5 3 5 3 3 1 4 1 5 2 3 3 2 4 4 5 1`  
12·30 12:30 字典序第 $19200000000001$ 小的方案：  
`1 2 3 1 5 1 4 2 5 3 4 5 4 3 2 2 4 3 1 3 5 5 2 4 1 3 2 4 5 3 1 1 2 1`  
12·30 22:30 字典序第 $20640000000001$ 小的方案：  
`1 2 3 1 5 2 1 4 5 4 5 1 1 5 3 1 2 5 3 5 3 1 2 1 2 4 2 1 5 3 1 1 2 1`  
1·1 00:00 字典序第 $21080000000001$ 小的方案：  
`1 2 3 1 5 2 3 4 5 4 1 5 5 3 1 5 1 1 4 3 2 5 3 1 5 3 5 2 2 4 4 3 5 1`  
1·1 12:30 字典序第 $22710000000001$ 小的方案：  
`1 2 3 1 5 3 2 4 1 5 4 3 1 2 4 2 3 3 4 1 2 5 2 3 5 3 4 1 5 2 1 1 3 1`  
1·1 23:30 字典序第 $25010000000001$ 小的方案：  
`1 2 3 1 5 4 3 2 1 3 2 5 5 3 2 2 4 1 3 1 4 3 5 2 5 2 5 1 1 4 4 3 5 1`  
1·2 11:30 字典序第 $25392000000001$ 小的方案：  
`1 2 3 1 5 4 3 2 5 3 5 4 5 2 3 5 1 1 3 5 3 3 4 1 2 5 2 3 3 4 1 1 2 1`  
1·2 16:30 字典序第 $26020000000001$ 小的方案：  
`1 2 3 4 3 1 4 2 3 5 4 1 4 3 2 4 1 2 5 4 3 1 4 2 1 5 2 4 1 5 3 2 3 1`  
1·2 22:30 字典序第 $26750000000001$ 小的方案：  
`1 2 3 4 3 1 4 5 4 3 5 4 4 3 2 5 1 2 4 2 1 3 5 3 4 2 5 1 2 5 4 3 4 1`  
1·3 12:30 字典序第 $27750000000001$ 小的方案：  
`1 2 3 4 3 2 1 5 4 5 3 2 1 5 3 1 3 4 2 1 2 1 5 4 3 1 2 4 3 2 1 1 3 1`  
1·3 22:30 字典序第 $29220000000001$ 小的方案：  
`1 2 3 4 3 4 1 2 1 2 1 4 5 1 5 1 3 3 5 1 5 1 2 4 3 1 5 4 5 1 1 2 3 2`  
1·4 12:30 字典序第 $30130000000001$ 小的方案：  
`1 2 3 4 3 4 1 5 3 5 4 2 3 5 3 4 1 3 2 3 2 5 1 5 1 3 1 2 2 3 3 2 4 1`  
1·4 22:30 字典序第 $31560000000001$ 小的方案：  
`1 2 3 4 3 4 5 2 1 2 4 1 1 3 1 4 5 5 2 4 3 3 1 3 5 1 2 4 5 2 1 1 3 1`  
1·5 22:30 字典序第 $33340000000001$ 小的方案：  
`1 2 3 4 3 5 4 1 4 2 3 1 1 2 3 5 3 3 1 4 5 1 5 3 1 2 1 3 1 4 3 2 3 1`  
1·6 12:30 字典序第 $34080000000001$ 小的方案：  
`1 2 3 4 5 1 2 3 4 2 4 3 5 3 5 5 1 3 2 4 5 4 1 5 2 3 5 1 3 4 1 1 2 1`  
1·6 22:30 字典序第 $35540000000001$ 小的方案：  
`1 2 3 4 5 1 4 3 4 3 2 1 4 5 2 5 2 3 1 4 2 5 4 3 5 3 1 4 1 2 4 4 5 1`  
1·7 12:30 字典序第 $36410000000001$ 小的方案：  
`1 2 3 4 5 2 3 1 3 5 4 2 3 1 3 3 2 4 5 3 2 5 2 1 5 3 5 1 4 2 3 4 5 1`  
1·7 22:30 字典序第 $37880000000001$ 小的方案：  
`1 2 3 4 5 3 1 2 4 1 5 4 4 1 2 4 5 1 2 4 5 3 5 1 3 2 1 5 2 4 4 3 5 1`  
1·8 12:30 字典序第 $38810000000001$ 小的方案：  
`1 2 3 4 5 3 4 1 4 1 3 2 5 4 2 4 3 3 1 4 3 2 4 5 1 2 5 4 1 2 4 4 5 1`  
1·8 22:30 字典序第 $40270000000001$ 小的方案：  
`1 2 3 4 5 4 1 3 2 3 4 1 1 2 3 2 5 4 3 2 1 5 2 1 5 2 1 4 4 2 2 3 4 1`  
1·9 12:30 字典序第 $41270000000001$ 小的方案：  
`1 2 3 4 5 4 2 3 5 1 2 4 5 3 2 3 4 1 2 1 5 5 4 5 3 1 5 2 3 4 4 3 5 1`  
1·9 21:30 字典序第 $42340000000001$ 小的方案：  
`1 2 3 4 5 4 3 2 5 3 5 4 5 2 1 4 1 1 5 4 3 5 4 2 5 2 5 3 5 4 2 2 3 1`