第45届ICPC杭州 L题 图着色问题

各位大佬麻烦看看我的代码有什么问题呀

我觉得这道题挺简单的，我把原来着色问题常用的贪心算法的OK函数改了一下，就是中间有没有相连的那个判断条件改了改。我测试了几个样例都是对的，但是提交答案通过率只有5.88%

#include<iostream>
using namespace std;
#define N 100
int Ok(int i,int permutation[N],int color[N],int n) {
for(int j=0; j<n; j++) {
if(((j<i&&permutation[j]>permutation[i])||(j>i&&permutation[j]<permutation[i]))&&(color[i]==color[j]))//对于顶点i广度遍历j个结点，对于和顶点i有连线的结点（相邻），如果颜色相同（有冲突）
return 0;
}
return 1;
}
void ColorGraph(int n){
int color[n];
int permutation[n];
int i;
for (i=0;i<n;i++)
{
scanf("%d",&permutation[i]);
}
int k=0,flag=1;
//flag=1表示图中还有未涂色的顶点
while(flag){//每一轮while会尽量先上色一种颜色，有冲突的会留下来继续上色
k++;//颜色种数
flag=0;//取下一种颜色
for(int i=0;i<n;i++){//对于每一个结点
if(!color[i]){//如果没有颜色
color[i]=k;//顶点i图颜色k（上色）
if(!Ok(i,permutation,color,n)){//发生冲突，取消涂色
color[i]=0;//不上色
flag=1;//还有未上色的顶点
}
}
}
}
cout<<k<<endl;
for(i=0;i<n;i++)
{
cout<<color[i]<<" ";
}
cout<<endl;
}
int main() {
int r;
int n;
scanf("%d",&r);//测试轮数
while(r--)
{
scanf("%d",&n);
ColorGraph(n);
}
return 0;
}

最后

以上就是自信蜗牛为你收集整理的第45届ICPC杭州 L题 图着色问题的全部内容，希望文章能够帮你解决第45届ICPC杭州 L题 图着色问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。