標題:
2022 B-防盜雷達
[打印本頁]
作者:
may
時間:
2025-3-25 18:33
標題:
2022 B-防盜雷達
B-防盜雷達
時間限制 1 秒 / 記憶體限制 1 G
某國國防部想要架設⾶彈偵測系統。
此系統由多個雷達組成，並且雷達與雷之間以無線網路串接。
當⾶彈來襲時，⼀但有雷達偵測到⾶彈，就會透過網路傳輸給其他所有的雷達。
由於如果相鄰的雷達之間使⽤相同的無線電波頻率，會造成訊號⼲擾。
因此若有保持系統正常運⾏，所有相鄰的雷達都必須使⽤不同的無線電波頻率。
另外，任兩個雷達之間都⼀定可以傳輸資料給對⽅，並且路徑唯⼀。
為了使成本下降，國防部想要知道最少需要使⽤多少種不同的無線電波頻率。
● 輸入說明
第⼀⾏輸入兩個整數N和M分別代表總共有N個雷達 (編號1~N)，以及總共有M組相鄰的雷
達。
接下來有M⾏，每⾏皆有兩個整數Xi，Yi代表雷達Xi與雷達Yi相鄰。
[attach]20824[/attach]
● 輸出說明
請輸出最少需要使⽤多少種不同的無線電波頻率。
範例輸入1
3 2
1 2
1 3
範例輸出1
2
範例輸入2
4 3
1 2
2 3
3 4
範例輸出2
2
作者:
may
時間:
2025-3-25 19:07
回復
1#
may
#include<bits/stdc++.h>
#define int long long //確保變數能夠處理較大的數值範圍，避免溢位。
using namespace std;
int n,m;
signed main()//因#define int long long而main 函數必須傳回一個int 值，所以不能使用int main()。通常使用signed main，因為signed 等效替代於signed int，也就是有符號整數，這與int 別無二致，並且不會導致奇怪的CE。
{
int a,b,ans=0;
cin>>n>>m;
vector<int> path[n+1];//path[i]：儲存與雷達 i 相鄰的所有雷達編號,n+1：確保陣列索引從 1 開始，與輸入數據一致。
int freq[n+1]={0}; //freq[i]：雷達 i 被分配的頻率值,初始化為 0，表示尚未分配頻率。
for(int i=0;i<m;i++)
{
cin>>a>>b;
path[b].push_back(a);
path[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
set<int> s; //set容器是用二元搜尋樹實現的一種集合，集合中每種元素只出現一次。count()是set容器中常用的函數。
for(int j=0;j<path[i].size();j++)
s.insert(freq[path[i][j]]);//建立 set<int> s，用來存放與 i 相鄰的雷達已經使用的頻率。freq[path[i][j]]：代表相鄰雷達 path[i][j] 的頻率，將這些頻率存入 set 中。
int index=1;
while(s.count(index))// set::count() 是C++ STL中的内置函数，它返回元素在集合中出现的次数。由于set容器仅包含唯一元素，因此只能返回1或0。
index++;
freq[i]=index;
ans=max(ans,index);
}
cout<<ans<<endl;
return 0;
}
複製代碼
----------------------------------------------
正確解法：使用 BFS 來檢查是否需要 2 或 1 種顏色
因為：
樹一定是連通的，且無環
樹總是二分圖（最多需要 2 種顏色）
我們可以用 BFS 或 DFS 來二分著色：
如果整棵樹只有 1 個節點，那麼只需要 1 種顏色。
否則，因為樹是二分圖，最少需要 2 種顏色。
------------------------------------------
解釋
建立鄰接表：
讀取 N 和 M。
用 adj[X].push_back(Y) 來存儲連接關係。
使用 BFS 進行二分著色：
用 queue<int> 來進行廣度優先搜索（BFS）。
color
存儲每個節點的顏色（1 或 2）。
若相鄰節點還沒染色，就賦予不同顏色，並加入隊列繼續搜尋。
輸出 2：
除非 N == 1，否則樹必定是二分圖，只需 2 種顏色。
時間複雜度分析
建構鄰接表： O(N)
BFS 遍歷所有節點： O(N)
總時間複雜度： O(N)
------------------------------
測資:
測資00：最小測資 (只有 1 個雷達)
輸入
1 0
預期輸出
1
解析：只有 1 個雷達，僅需 1 種頻率。
測資 01：鏈狀樹
輸入
5 4
1 2
2 3
3 4
4 5
預期輸出
2
解析：這是一條線狀樹，像這樣：
1 - 2 - 3 - 4 - 5
可以使用交替頻率（例如 1, 2, 1, 2, 1），因此最多只需要 2 種頻率。
測資 02：星狀樹
輸入
6 5
1 2
1 3
1 4
1 5
1 6
預期輸出
2
解析：這是 星狀樹，所有雷達都連接到節點 1：
2
|
1 - 3
|
4
|
5
|
6
可以讓 1 使用顏色 1，其他所有相鄰節點 (2, 3, 4, 5, 6) 使用顏色 2，所以只需要 2 種顏色。
測資 03：完全二元樹
輸入
7 6
1 2
1 3
2 4
2 5
3 6
3 7
預期輸出
2
解析：這是一棵二元樹：
1
/ \
2 3
/ \ / \
4 5 6 7
根節點 1 使用顏色 1
2 和 3 使用顏色 2
4, 5, 6, 7 使用顏色 1
因此只需要 2 種頻率。
測資 04：隨機樹
輸入
8 7
1 2
1 3
2 4
2 5
3 6
3 7
6 8
預期輸出
2
解析：
1
/ \
2 3
/ \ / \
4 5 6 7
|
8
仍然是二分圖，最多只需要 2 種頻率。
這 5 筆測資涵蓋了： ✅ 最小情況 (N=1)
✅ 線性結構（鏈狀樹）
✅ 星狀樹
✅ 完全二元樹
✅ 隨機樹
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
