数据结构-图着色问题

7-38 图着色问题 （25 分）

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V（0

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出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，大于小于都不行，划重点。

其他地方就没有难度了。

#include

#include

#include

#include

using namespace std;

#define maxn 505

int map[maxn][maxn],judge[maxn][maxn];

int color[maxn],tong[maxn];

int n,m,k;

int cmp(int a,int b)

{

return a>b;

}

void init()

{

for(int i = 1; i <= n; i ++)

for(int j = 1; j <= n; j ++)

map[i][j] = maxn;

}

int main()

{

scanf("%d%d%d",&n,&m,&k);

init();

for(int i = 0; i < m; i ++)

{

int x,y;

scanf("%d %d",&x,&y);

map[x][y] = map[y][x] = 1;

}

int t;

scanf("%d",&t);

while(t--)

{

int flag = 0;

memset(tong,sizeof(tong));

for(int i = 1; i <= n; i ++)

{

scanf("%d",&color[i]);

int temp = color[i];

tong[temp]++;

}

sort(tong,tong+501,cmp);

for(int i = 0; i < maxn; i ++)

{

if(tong[i])

flag++;

else

break;

}

int index = 0;

if(flag>k||flag

printf("Non");

else if(!m)

printf("Yesn");

else

{

for(int i = 1; i <= n; i ++)

{

for(int j = i + 1; j <= n; j ++)

{

if(map[i][j]!=maxn&&color[i]!=color[j])

index ++;

else if(map[i][j]==maxn)

continue;

else if(map[i][j]!=maxn&&color[i]==color[j])

{

index = -1;

break;

}

}

if(index == -1)

break;

}

if(index == m)

printf("Yesn");

else

printf("Non");

}

}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!