[演算法心得] UVA 193. Graph Coloring
嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 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，只要塗黑色那相鄰的點勢必要塗白色，這樣大大的減少數量。
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MXN = 200005;
int ans = 0;
int n = 0, m = 0, k = 0;
vector<int> pathAns, color;
vector<vector<int> > path;
void dfs(int idx, int c){
if(idx > n){
if(ans < c){
ans = c;
for(int i = 1; i <= n; ++i){
pathAns = color;
}
}
return;
}
for(int i = idx; i <= n; ++i){
if(n - idx + c + 1 <= ans) return; // 剪枝，如果當前畫最多黑色仍然不足ans就退出。
if(color == 0){
color = i;
for(int j : path) if(color == 0) color = i;
int now = i;
while(color && now <= n) now++;
dfs(now, c + 1);
for(int j = 1; j <= n; ++j) if(color == i) color = 0;
}
}
}
void sol(){
ans = 0;
cin >> n >> m;
path.clear();
pathAns.clear();
color.clear();
path.resize(n + 1);
pathAns.resize(n + 1);
color.resize(n + 1);
for(int i = 0; i < m; ++i){
int s, t;
cin >> s >> t;
path.emplace_back(t);
path.emplace_back(s);
}
dfs(1, 0);
cout << ans << '\n';
int flag = 0;
for(int i = 1; i <= n; ++i){
if(pathAns == i){
if(flag){
cout << ' ';
}
cout << i;
flag = 1;
}
}
cout << '\n';
}
int main(){
io
int t = 1;
cin >> t;
while(t--){
sol();
}
}
頁:
[1]