[思维][贪心] UVa1613 K-Graph Oddity

先说结论:构造的方法就是以任意一个点开始dfs,对于dfs到的点,把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值,比如和它相邻有4个点,其中3个分别为1,3,3,另一个未染色,那么就把当前的颜色设置为2。

这个做法,网上并没有找到一个说得过去的证明,我自己也无法严格证明贪心过程的正确性,也没有找到官方题解,就是很玄学。而且,同样的贪心过程,如果先对一个点先dfs再染色,也就是根据子孙节点的颜色修改当前的颜色,就会出现某个节点大于k的情况(虽然仍然是保证了不同点之间不同染色),但是如果先染色再dfs,也就是先处理好搜索过的节点,根据祖先节点修改当前的节点,就能保证通过所有数据。

 

//#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=10000+5;
const int mod=1e9+7;

vector G[maxn];
int vis[maxn],color[maxn],cc[maxn],ak,n;

void dfs(int k)
{
    if(vis[k]!=-1)
        return ;
    vis[k]=1;
    int len=G[k].size();
    for(int i=0;i
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据