難得解個題
做個筆記
給定一張圖
點可以塗黑或塗白,黑色不相鄰
求最多可以塗多少黑點
一開始自以為greedy的直覺
"既然要塗最多黑色,那就把連結數最少的點塗黑吧,然後一路塗完..."
都說是自以為了,理所當然是錯的
google "ACM 193" 前幾個連結就有在討論這個,也有人提出了反例
所以只好乖乖暴力法了
暴力法的想法
"一個點非黑即白 所以只要把一個點塗黑 繼續塗完整張圖,
或者塗白 繼續塗完整張圖"
就可以找到所有結果
擺明可以遞迴,所以就遞迴求解
遞回函式的想法大概是
1. 選定還沒塗色的點,塗黑,並把相鄰點塗白 剩下的點遞迴求解
2. 把剛剛這個點塗白,遞迴求解
3. 整張圖都塗色了,判斷是否為最大值
code :
#include int n,k; int graph[101][101]; int max; int maxList[101]; int color[101]; void draw(){ int finish = 1; int current[101]; for(int i = 1; i <= n; ++i){ current[i] = color[i]; } for(int i = 1; i <= n; ++i){ if(color[i] == 0){ finish = 0; color[i] = 2; for(int j = 1; j <= n; ++j){ if(graph[i][j] == 1 && color[j] == 0){ color[j] = 1; } } draw(); color[i] = 1; for(int j = 1; j <= n; ++j){ color[j] = current[j]; } color[i] = 1; } } if(finish == 1){ int count = 0; for(int i = 1; i <= n; ++i){ if(color[i] == 2){ ++count; } } if(count > max){ max = count; count = 0; for(int i = 1; i <= n; ++i){ if(color[i] == 2) maxList[count ++] = i; } } } } int main(){ int c; scanf("%d", &c); for(int i = 0; i < c; ++i){ max = 0; for(int x = 1 ; x < 101; ++x){ maxList[x] = 0; color[x] = 0; for(int y = 1 ; y < 101; ++y) graph[x][y] = 0; } scanf("%d%d", &n, &k); for(int j = 0; j < k; ++j){ int to , from; scanf("%d%d", &to, &from); graph[to][from] = 1; graph[from][to] = 1; } draw(); printf("%d\n", max); printf("%d", maxList[0]); for(int i = 1; i < max; ++i) printf(" %d", maxList[i]); printf("\n"); } }
沒有留言:
張貼留言