?

題目大意

?

有 n(1≤n≤3*10⁵) 匹馬，每條馬都有幾個敵人（不超過 3 個），現(xiàn)在要求把這些馬分成兩部分（允許一部分中沒有一條馬），使得對于每條馬，和它在同一部分中的敵人的數(shù)量不超過1個

給出了所有的敵對關(guān)系，求一個劃分的方案。如果不存在劃分方案，輸出-1

?

做法分析

?

首先，觀察下為什么題目給的數(shù)據(jù)范圍這么奇葩：

每條馬的敵人的數(shù)量不超過 3 個

這有什么用呢？想了很久，畫了好幾個圖，最終確定，這樣的條件下，一定是存在一個劃分方案，使得每部分中，每條馬的敵人數(shù)量不超過 1 個。

可以考慮 4 個點的完全圖，每個點的度是 3，對應(yīng)了 3 個敵人，我們完全可以找出一種分配的方案使得這個圖的點分成兩個點集，那么，對于其余的情況，肯定也是能夠找出一種解的，因為他們的關(guān)系比 4 個點的完全圖的關(guān)系更加的簡單

也就是說，輸出 -1 的情況是不存在的

接下來就考慮怎么構(gòu)造出一種分配的方案了

?

實在是想不出有什么其他的做法了，干脆貪心的找找，類似于 SPFA 的 BFS：

? ? ? ? ①. 先假設(shè)所有的馬都在同一個部分中，把所有不合格的馬（有超過 1 個敵人的）入隊

? ? ? ? ②. BFS 的過程中，先把當(dāng)前馬移動到另一個部分中，然后再統(tǒng)計它的敵人中，哪些馬變得不合法了，把不合法的加入到隊列中

這樣不斷的 BFS，肯定能夠找到一種分配方案，但是具體的時間復(fù)雜度不知道怎么計算的，迷迷糊糊的就過了......

?

參考代碼

?

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 const int N=300006; 9 10 int arc[N][10], n, m, ans[N]; 11 queue <int> q; 12 13 bool Ok(int u) 14 { 15 int cnt=0; 16 for(int i=1; i<=arc[u][0]; i++) 17 { 18 int v=arc[u][i]; 19 if(ans[u]==ans[v]) cnt++; 20 } 21 return cnt<2; 22 } 23 24 void BFS() 25 { 26 while(!q.empty()) q.pop(); 27 for(int i=1; i<=n; i++) 28 if(!Ok(i)) q.push(i); 29 while(!q.empty()) 30 { 31 int u=q.front(); 32 q.pop(); 33 if(Ok(u)) continue; 34 ans[u]^=1; 35 for(int i=1; i<=arc[u][0]; i++) 36 if(!Ok(arc[u][i])) q.push(arc[u][i]); 37 } 38 } 39 40 int main() 41 { 42 scanf("%d%d", &n, &m); 43 for(int i=1; i<=n; i++) ans[i]=0, arc[i][0]=0; 44 for(int i=0, a, b; i<m; i++) 45 { 46 scanf("%d%d", &a, &b); 47 arc[a][++arc[a][0]]=b; 48 arc[b][++arc[b][0]]=a; 49 } 50 BFS(); 51 for(int i=1; i<=n; i++) printf("%d", ans[i]); 52 printf("\n"); 53 return 0; 54 } C. Dima and Horses

?

題目鏈接 & AC通道

?

Codeforces Round #167 (Div. 1) C. Dima and Horses

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhj5chengfeng/archive/2013/05/30/3108783.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #167 (Div. 1) C. Dima and Horses（BFS+贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。