P2819 图的m着色问题

admin

https://www.luogu.org/problemnew/show/P2819

题目背景
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

题目描述
对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。

输入输出格式
输入格式：
第1行有3个正整数n，k 和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。

输出格式：
程序运行结束时，将计算出的不同的着色方案数输出。

输入输出样例
输入样例#1：
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
输出样例#1：
48
说明
n<=100;k<=2500;

在n很大时保证k足够大。

保证答案不超过20000。

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,k,m,ans=0;///n个点 k条边 m种颜色
   
4. const int mx=110;
   
5. int a[mx];///颜色
   
6. bool b[mx][mx];///b判断两点是否连通
   
7. bool check(int x)
   
8. {
   
9.     for (int ix=1;ix<=n;ix++)
   
10.     {
    
11.         if (b[ix][x]&&a[x]==a[ix])
    
12.             return false;
    
13.     }
    
14.     return true;
    
15. }
    
16. void dfs(int i)
    
17. {
    
18.     if (i>=n+1) ans++;
    
19.     else for (int j=1; j<=m; j++)
    
20.         {
    
21.             a[i]=j;///第i个顶点填第j种颜色
    
22.             if (check(i))///如果可以
    
23.                 dfs(i+1);
    
24.             a[i]=0;
    
25.         }
    
26. }
    
27. int main()
    
28. {
    
29.     cin>>n>>k>>m;
    
30.     for (int i=1; i<=k; i++)
    
31.     {
    
32.         int x,y;
    
33.         cin>>x>>y;
    
34.         b[x][y]=true;
    
35.         b[y][x]=true;///连通
    
36.     }
    
37.     dfs(1);
    
38.     cout<<ans;
    
39.     return 0;
    
40. }
    

复制代码

张笑宇

不确定是否要用“图论”~~~~

胡雨菲菲

爆搜

1. #include <cstdio>
   
2. 
   
3. const int N = 110, M = 2510;
   
4. 
   
5. struct Edge {
   
6.     int v, nex;
   
7. }edge[M << 1]; int top, e[N];
   
8. 
   
9. inline void add(int x, int y) {
   
10.     top++;
    
11.     edge[top].v = y;
    
12.     edge[top].nex = e[x];
    
13.     e[x] = top;
    
14.     return;
    
15. }
    
16. 
    
17. int k, n, ans, cl[N];
    
18. 
    
19. void DFS(int x) {
    
20.     if(x == n + 1) {
    
21.         ans++;
    
22.         return;
    
23.     }
    
24.     for(int i = 1; i <= k; i++) { /// color
    
25.         bool f = 1;
    
26.         for(int j = e[x]; j; j = edge[j].nex) {
    
27.             int y = edge[j].v;
    
28.             if(y > x) {
    
29.                 continue;
    
30.             }
    
31.             if(cl[y] == i) {
    
32.                 f = 0;
    
33.                 break;
    
34.             }
    
35.         }
    
36.         if(f) {
    
37.             cl[x] = i;
    
38.             DFS(x + 1);
    
39.         }
    
40.     }
    
41.     return;
    
42. }
    
43. 
    
44. int main() {
    
45.     int m;
    
46.     scanf("%d%d%d", &n, &m, &k);
    
47.     for(int i = 1, x, y; i <= m; i++) {
    
48.         scanf("%d%d", &x, &y);
    
49.         add(x, y);
    
50.         add(y, x);
    
51.     }
    
52.     DFS(1);
    
53.     printf("%d", ans);
    
54.     return 0;
    
55. }
    

复制代码

type尧

1. 
   

复制代码

Charleyxiao

链式前向星最好了（逃

1. //P2819
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. const int maxn=10010;
   
5. int n,k,m,ans=0,color[maxn],tot=0,vis[maxn],ver[maxn],nxt[maxn],head[maxn];
   
6. inline void add(int x,int y){
   
7.         ver[++tot]=y;
   
8.         nxt[tot]=head[x];
   
9.         head[x]=tot;
   
10. }
    
11. inline bool valid(int c,int p){
    
12.         for(int i=head[p];i;i=nxt[i]){
    
13.                 int y=ver[i];
    
14.                 if(color[y]==c) return 0;
    
15.         }
    
16.         return 1;
    
17. }
    
18. void dfs(int dep){
    
19.         if(dep==n+1) return ans++,void();
    
20.         for(int i=1;i<=m;++i){
    
21.                 if(valid(i,dep)){
    
22.                         color[dep]=i;
    
23.                         dfs(dep+1);
    
24.                         color[dep]=0;
    
25.                 }
    
26.         }
    
27. }
    
28. int main(){
    
29.         ios::sync_with_stdio(0);
    
30.         cin>>n>>k>>m;
    
31.         for(int i=1;i<=k;++i){
    
32.                 int u,v;
    
33.                 cin>>u>>v;
    
34.                 add(u,v);
    
35.                 add(v,u);
    
36.         }
    
37.         dfs(1);
    
38.         cout<<ans<<endl;
    
39.         return 0;
    
40. }

复制代码