poj 1419 Graph Coloring uva 193 - Graph Coloring (图着色有关问题，dfs)
题目大意：图的着色问题。给定一个无向图（不一定连通），给图中的点涂上黑白两种颜色，但相邻的两个点不能全是黑色。任务是算出最多可以涂上几个黑点。
解题思路：依次判断每个点能不能涂成黑色，然后会有三种情况（就是这三条路，沿着这三条路一直往下遍历，就ok）
第一条：如果邻接点已经有了黑点，则改点不能再涂黑色了，直接往下遍历即可，这是一条路，与后面的两条路没有牵扯，所以后面加上return表示一种情况；
第二条和第三条：如果邻接点没有黑点，那么改点的涂法就可以有两种，每种都要遍历一下，继续往下走即可。
注意自己控制好边界条件。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int G[110][110];
int color[110];
int ans[110];
int n,m;
int max_;
void dfs(int cur,int black_num)
{
if(cur > n)
{
if(black_num>max_)
{
max_=black_num;
memcpy(ans,color,sizeof(color));
}
return;
}
for(int v = 1;v<=n;v++)
{
if(G[cur][v]&&color[v])
{
dfs(cur+1,black_num);
return;
}
}
color[cur]=1;
dfs(cur+1,black_num+1);
color[cur]=0;
dfs(cur+1,black_num);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(G,0,sizeof(G));
memset(color,0,sizeof(color));
scanf("%d%d",&n,&m);
int a1,a2;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a1,&a2);
G[a1][a2]=G[a2][a1]=1;
}
max_=0;
dfs(1,0);
printf("%d\n",max_);
int flag=0;
for(int i=1;i<=n;i++)
{
if(ans[i])
{
if(flag)
printf(" ");
printf("%d",i);
flag=1;
}
}
printf("\n");
}
return 0;
}
这道题算很简单的回溯题目，却断断续续做了三次没有能AC，最后还是看了题解，然后马上就有了一条非常清晰的思路。简单利落的写出来，然后一遍过掉。
为什么前两次做的时候会那么迷茫地用错误的思路得到同样的wrong？这是值得我深思的。
一方面因为自己读题的时候就没能完全把握住题意，对题目所给出的任务并不明确。造成这种结果的原因，并不能简单归咎于英语问题的不大好理解。通过昨天的校内赛，再加上自己之前的总结，可以明确地告诉自己，对任务的准确和快速把握，是练ACM的强大技能之一。在这一方面，并不是你的英语好你就占尽优势，因为对所给任务的把握，你应该综合各方面的信息。比如，你需要找准题目描述中哪段话告诉的哪段信息是对自己有用的，时透露给自己某种边界信息，或是对自己解题思路的形成有一定的指导作用，这项技能需要你做大量的题目，从中寻找灵感，发现规律，或是神奇的就是会有某种感觉。然后是你对所给样例的揣摩，有些题目有些人可以直接不看题目而从样例中明白任务的具体内容，从而快速Ac题。对于我们来说，即使不能看样例做题，也一定能从样例中获得不可忽视的启发，对解题思路的形成会有巨大帮助。
另外一个比较神的说法就是自己对题目的感觉，也许你不知道为什就会有这种感觉，可你就是有这种感觉。我就觉得这道题这样来干就能AC，那你就这样去干。
总之，准确获取任务很重要，任务不明确你还费什么功夫呢？下了功夫，也是越来越迷茫~。