[演算法心得] UVA 193. Graph Coloring

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: Graph Coloring
題目網站: Uva
題目網址: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=129
題目內容:

You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes ofthe graph and the only available colors are black and white.The coloring of the graph is called optimal if a maximum ofnodes is black. The coloring is restricted by the rule that notwo connected nodes may be black.

題目大意:

給你一張圖，要求你塗色，限制是塗黑色之間不能相鄰，而塗白色沒有限制。問最多能圖幾個黑色。

範例輸入 #1:
1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

範例輸出 #1:
3
1 4 5
--------------------------------------------------- 題解心得 ---------------------------------------------------

這題分析一下有點像最大獨立集，但是就算優化過後的時間複雜度仍為 O(1.1888 ^ n)，他總共有 100 個點，時間限制只有 3 秒，顯然會TLE。
所以換一條思路，如果直接DFS，只要塗黑色那相鄰的點勢必要塗白色，這樣大大的減少數量。

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 200005;
   
8. int ans = 0;
   
9. int n = 0, m = 0, k = 0;
   
10. vector<int> pathAns, color;
    
11. vector<vector<int> > path;
    
12. 
    
13. void dfs(int idx, int c){
    
14.   if(idx > n){
    
15.     if(ans < c){
    
16.       ans = c;
    
17.       for(int i = 1; i <= n; ++i){
    
18.         pathAns[i] = color[i];
    
19.       }
    
20.     }
    
21.     return;
    
22.   }
    
23.   for(int i = idx; i <= n; ++i){
    
24.     if(n - idx + c + 1 <= ans) return; // 剪枝，如果當前畫最多黑色仍然不足ans就退出。
    
25.     if(color[i] == 0){
    
26.       color[i] = i;
    
27.       for(int j : path[i]) if(color[j] == 0) color[j] = i;
    
28.       int now = i;
    
29.       while(color[now] && now <= n) now++;
    
30.       dfs(now, c + 1);
    
31.       for(int j = 1; j <= n; ++j) if(color[j] == i) color[j] = 0;
    
32.     }
    
33.   }
    
34. }
    
35. 
    
36. void sol(){
    
37.   ans = 0;
    
38.   cin >> n >> m;
    
39.   path.clear();
    
40.   pathAns.clear();
    
41.   color.clear();
    
42.   path.resize(n + 1);
    
43.   pathAns.resize(n + 1);
    
44.   color.resize(n + 1);
    
45.   for(int i = 0; i < m; ++i){
    
46.     int s, t;
    
47.     cin >> s >> t;
    
48.     path[s].emplace_back(t);
    
49.     path[t].emplace_back(s);
    
50.   }
    
51.   dfs(1, 0);
    
52.   cout << ans << '\n';
    
53.   int flag = 0;
    
54.   for(int i = 1; i <= n; ++i){
    
55.     if(pathAns[i] == i){
    
56.       if(flag){
    
57.         cout << ' ';
    
58.       }
    
59.       cout << i;
    
60.       flag = 1;
    
61.     }
    
62.   }
    
63.   cout << '\n';
    
64. }
    
65. 
    
66. int main(){
    
67.   io
    
68.   int t = 1;
    
69.   cin >> t;
    
70.   while(t--){
    
71.     sol();
    
72.   }
    
73. }

複製代碼