題干：

L2-3?圖著色問題?（25?分)

圖著色問題是一個著名的NP完全問題。給定無向圖G=(V,E)，問可否用K種顏色為V中的每一個頂點分配一種顏色，使得不會有兩個相鄰頂點具有同一種顏色？

但本題并不是要你解決這個著色問題，而是對給定的一種顏色分配，請你判斷這是否是圖著色問題的一個解。

輸入格式：

輸入在第一行給出3個整數V（0<V≤500）、E（≥0）和K（0<K≤V），分別是無向圖的頂點數、邊數、以及顏色數。頂點和顏色都從1到V編號。隨后E行，每行給出一條邊的兩個端點的編號。在圖的信息給出之后，給出了一個正整數N（≤20），是待檢查的顏色分配方案的個數。隨后N行，每行順次給出V個頂點的顏色（第i個數字表示第i個頂點的顏色），數字間以空格分隔。題目保證給定的無向圖是合法的（即不存在自回路和重邊）。

輸出格式：

對每種顏色分配方案，如果是圖著色問題的一個解則輸出Yes，否則輸出No，每句占一行。

輸入樣例：

6 8 3 2 1 1 3 4 6 2 5 2 4 5 4 5 6 3 6 4 1 2 3 3 1 2 4 5 6 6 4 5 1 2 3 4 5 6 2 3 4 2 3 4

輸出樣例：

Yes Yes No No

解題報告：?

? ? ?剛開始讀錯題了一直不知道這個K是干嘛用的，后來發現是能切只能用K個顏色，而不是1~K這些個顏色，，研究樣例就慢慢讀懂題意了。代碼很簡單，枚舉每條邊判斷就可以了。

AC代碼：

#include<bits/stdc++.h> #define pb push_back typedef long long ll; using namespace std; const int MAX = 2e6 + 5; pair<int,int> p[MAX]; int col[MAX]; int main() {int n,m,k;cin>>n>>m>>k;for(int i = 1; i<=m; i++) {scanf("%d%d",&p[i].first,&p[i].second);}int q;cin>>q;while(q--) {int flag = 1;set<int> ss;for(int i = 1; i<=n; i++) {scanf("%d",&col[i]);ss.insert(col[i]);}if(ss.size() != k) flag = 0;if(flag == 1) {for(int i = 1; i<=m; i++) {if(col[p[i].first] == col[p[i].second]) {flag = 0;break;}}}if(flag) puts("Yes");else puts("No");}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【PTA天梯赛CCCC -2017决赛L2-3】图着色问题 （25 分)（图染色）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。