POJ 1129-Channel Allocation(四色定理+迭代深搜)
題目鏈接:傳送門
題意:n個信號站,給出連接情況,要用信號覆蓋所有信號站,要求相連的信號站不能用同一個信號。
等價問題==無向圖染色==四色定理(每個平面地圖都可以只用四種顏色來染色,而且沒有兩個鄰接的區域顏色相同。已證明)
思路:深搜一條路(枚舉顏色,判斷當前點用已有的顏色能不能染,如不能則加一種顏色,判斷強判就行了),搜到頭答案就出來了。。然後返回就可以了
注意單復數。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include