LOJ2406 随机

题目链接：

https://loj.ac/p/2406

我想无论什么图都是有解的。

每个点最多连出去7个点，有4种颜色，最多可以和一个相邻的点颜色相同。

考虑一个8个点的完全图，发现也有合法状态。

一开始想着，先给图搞一手两两匹配，缩点，缩完之后再普通四色染图...但是似乎有点复杂了。

但最终发现，合法状态似乎挺多，而且很容易构造。

暴力构造回溯复杂度似乎比较悬...

看了大佬们的程序，发现可以随机给每个点染色，然后再把当前不合法的点拿出来，挑一个附近一圈点数量最少的颜色，换上。

这样的话，最多增加1个新的不合法的点，甚至可能减少不合法点的数量。

在一定次数的调整之后，图就合法了。

不得不说太神奇了。

 1 #include
 2 const int N=3e4+10;
 3 int he[N],tot=0,ne[N*10],t[N*10],cc[N];
 4 int q[N*20];
 5 void link(int x,int y)
 6 {
 7     tot++;
 8     ne[tot]=he[x];
 9     he[x]=tot;
10     t[tot]=y;    
11 }
12 int che(int x,int y)
13 {
14     int ret=0;
15     for (int i=he[x];i;i=ne[i]) if (cc[t[i]]==y) ret++;
16     return ret;    
17 }
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while (T)
23     {
24         T--;
25         int n,m;
26         scanf("%d%d",&n,&m);
27         tot=0;
28         for (int i=1;i<=n;i++) he[i]=0,cc[i]=rand()%4;
29         for (int i=1;i<=m;i++)
30         {
31             int x,y;
32             scanf("%d%d",&x,&y);
33             link(x,y);
34             link(y,x);    
35         }
36         int k=0;
37         for (int i=1;i<=n;i++) if (che(i,cc[i])>1) q[++k]=i;
38         int i=0;
39         while (i<k)
40         {
41             i++;
42             int x=q[i];
43             if (che(x,cc[x])<=1) continue;
44             int mn=8,pp;
45             for (int j=0;j<=3;j++) if (che(x,j)j;
46             cc[x]=pp;
47             for (int j=he[x];j;j=ne[j]) if (cc[t[j]]==pp&&che(t[j],pp)>1) q[++k]=t[j];    
48         }
49         for (int i=1;i<=n;i++) printf("%c",cc[i]+'a');
50         printf("\n");
51     }
52 }