網頁

2014年3月9日 星期日

UVa 193 Graph Coloring

題意:
    黑色不能相鄰,白色則不限制,如果編號最大的點是黑色的,則稱這個填入方法為optimal。題目給定一個graph,求填入最多黑色的方法,如果有多個答案,則盡可能選擇optimal的那種。

想法:
    MaxNum為填入最多黑色的點的數量,透過backtracking找出多種填入的方式,並不斷刷新MaxNum,並將該填法記錄下來,最後輸出最大MaxNum的填入方式,詳細見底下code。