題目鏈接：https://www.luogu.org/problemnew/show/P1330 思路：參考過大佬的思路，第一次用染色思想寫題。提取題目的關鍵： （1）一條邊相連的點只至少有一個被占領。 （2）相鄰兩個點不能都被占領。 （1） + （2） ——> （3）相鄰兩個點有且只有一個點要被占 ...
題目鏈接：https://www.luogu.org/problemnew/show/P1330
思路：參考過大佬的思路（這句話是寫給那些杠精看的，其他看解析的忽略），第一次用染色思想寫題。提取題目的關鍵：
（1）一條邊相連的點只至少有一個被占領。
（2）相鄰兩個點不能都被占領。
（1） + （2） ——> （3）相鄰兩個點有且只有一個點要被占領。
染色思想：（2）相鄰兩個點不能都被占領。那麼我們可以把相鄰的兩個點標記為不同的符號，即可以認為染成不同的顏色。
可以結合題目，我們只需要兩種顏色就好，我這裡為黑和白。
該題為無向圖，可能還不是連通圖，題目也沒講是不是連通圖（就是所有點都可以連在一起），他可能有很多的子圖在學校里，
我們可以用dfs的思想，從一個點出發去染色，因為是無向圖，我們可以判斷，從一個點出發回到這個點，如果該點已經被染的顏色和dfs回來之後又要被染得顏色相同（參考上面的染色思想），
說明這樣染色是正確的，說明這個子圖可以被部分染色，慢慢的變為全部可以被染色，再得出答案，基本思路就是這樣。
那麼我們怎麼判斷需要最少幾個點被占領呢，我們知道，一個子圖如果可以全部染色，那麼，子圖上只有兩種顏色，黑色，白色，那我們只要取min(黑，白)就好了，
而且，這裡的黑白其實作用是一樣的（thinking...），代表占領而已，那麼如果有很多的子圖，我們可以讓每個子圖都ans += min（黑，白），
最後我們得到的ans就是最少需要占領的點了，在跑程式中，我們當然需要判斷能不能符合（3），即相鄰兩個點顏色不一樣，下麵代碼會有些解釋。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <string> 6 #include <vector> 7 using namespace std; 8 9 typedef long long LL; 10 #define inf (1LL << 30) - 1 11 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 12 #define rep__(i,j,k) for(int i = (j); i < (k); i++) 13 #define per(i,j,k) for(int i = (j); i >= (k); i--) 14 #define per__(i,j,k) for(int i = (j); i > (k); i--) 15 16 const int N = 10010; 17 vector<int> G[N];//存邊 18 bool vis[N]; //該點有沒有被訪問過 19 int col[N];//每個點的顏色記錄 20 int white,black;//全局的 21 int n,m; 22 int u,v; 23 int ans; 24 25 void input(){ 26 //無向圖，兩個互相存儲 27 rep(i,1,m){ 28 cin >> u >> v; 29 G[u].push_back(v); 30 G[v].push_back(u); 31 } 32 } 33 34 bool dfs(int now,int color){ 35 36 bool ok = true; //標記一下該dfs分支可以成功染色，即可以部分染色 37 38 if(vis[now]){ //如果回到了這個點，判斷該點的顏色是不是和要被染的顏色一樣 39 if(col[now] == color) return true;//一樣，說明該部分染色成功 40 else return false;//不一樣，直接一層層退出dfs 41 } 42 //沒被染色 43 else{ 44 vis[now] = true;//標記訪問 45 col[now] = color;//標記顏色 46 //統計顏色，~（-1） = 0 47 if(~color) ++white; 48 else ++black; 49 50 51 rep__(o,0,(int)G[now].size()){ 52 ok = dfs(G[now][o],-color); //判斷dfs分支能不能全部染色 53 if(!ok) break;//不能直接一層層退出dfs 54 } 55 } 56 57 return ok;//返回結果 58 } 59 60 bool all_blocked(){ 61 62 bool ok = true;//來一個標記，判斷每個子圖是不是都能被染色 63 int color = -1;//1表示白色，-1表示黑色 64 rep(i,1,n){ 65 66 white = black = 0; //每個子圖，需要初始化一下 67 //(！！！！)這裡說明下，因為是無向圖，那麼通過一個點一定可以遍歷該連通圖的所有的點 68 if(!vis[i]){ //該點是否被訪問，如果進入了下麵的程式，說明是另一個子圖， 上面（!!!!!）說了 69 ok = dfs(i,color); //dfs返回值為bool，true表示該子圖可以被全部染色 70 if(!ok) break;//false的話說明不能，直接退出，返回false 71 else ans += min(white,black); //可以的話統計最少需要占領的點數 72 } 73 } 74 75 return ok; 76 } 77 78 int main(){ 79 80 ios::sync_with_stdio(false); 81 cin.tie(0); 82 83 cin >> n >> m; 84 input(); //輸入 85 86 //如果能都被染色，輸出答案 87 if(all_blocked()) cout << ans << endl; 88 else cout << "Impossible" << endl; 89 90 getchar();getchar(); 91 return 0; 92 }
