【GPLT】L2-023 圖着色問題

2019 年 11 月 8 日
筆記

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/88766279

題目描述：

圖着色問題是一個著名的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

解題思路：

因為題目沒有給出路徑權值，只知道是否存在通路，所以可以直接用bool型變量記錄道路信息。用isLegal來判斷顏色分配方案是否合法（人之初性本善，萬物一開始都是好的，所以初始化為true），用一個set來記錄每次輸入的色號，若該色號已經出現過，則判斷相同顏色的倆個頂點是否相鄰，若色號相同的倆個頂點相鄰的話就令isLegal為false。最後需要注意的是！需要判斷顏色的種類數set.size()和題目給出的顏色數K是不是相等的，若不相等則令isLegal為false。我一開始傻逼了，寫的if(set.size()>K)，我咩起色號種類數小於K也沒事，然而有個測試點被扣了2分，沒有AC只有23，然後我還找半天不曉得錯在哪裡啦?。

AC代碼：

#include <bits/stdc++.h>  using namespace std;    int main()  {      int V,E,K;  //頂點數V,邊數E,顏色數K      cin >> V >> E >> K;      bool Edge[V+1][V+1];      memset(Edge,false,sizeof(Edge));  //初始化道路信息      for(int i = 0; i < E; i++)      {          int x,y;          cin >> x >> y;          Edge[x][y] = Edge[y][x] = true;  //相鄰的為true      }      int N;      cin >> N;      while(N--)      {          bool isLegal = true;  //判斷顏色分配方案是否合法          int a[V];          set<int> s;          for(int i = 1; i <= V; i++)          {              cin >> a[i];              if(s.count(a[i]) != 0)              {                  for(int j = 1; j < i; j++)                  {                      if(a[i] == a[j] && Edge[i][j])   //若存在頂點j和頂點i顏色相同,且頂點i、j是相鄰頂點                      {                          isLegal = false;                      }                  }              }              s.insert(a[i]);          }          if(s.size() != K)   //這裡有個測試點,必須要寫不等於,我之前寫的大於,只有23分          {              isLegal = false;          }          if(isLegal)          {              cout << "Yes" << endl;          }          else          {              cout << "No" << endl;          }      }      return 0;  }