学步园

其实这道题难度不大的，只不过图论的染色问题好久没写过了（记得上次写估计还是高一吧...），所以写的时候又查了些时间，现在写完了，就干脆记到这吧~

这道题要求相邻（距离不大于20）的两个塔之间的频段不相同，即可以与着色问题相联系，即相邻两个点的颜色不同，这样这道题就成了典型的着色问题。

直接看代码注释解释更方便：

#include <iostream><br /> #include <cstring><br /> using namespace std;<br /> int n;<br /> int color[12];<br /> int colornum;<br /> bool f[12][12];<br /> bool ok(int k,int x)<br /> {<br /> for (int i=0;i<n;i++)//判断与结点k相邻的结点与k结点的颜色x是否相同<br /> if (f[k][i] && x==color[i]) return false;<br /> return true;<br /> }<br /> void dfs(int k,int x)//k表示当前结点，x表示当前已使用的颜色数<br /> {<br /> if (x>=colornum) return;//若当前已使用的颜色>=最少颜色数，则返回<br /> if (k==n)//若结点都着完色，则更新colornum，注意，这时的x肯定比colornum小，是更优值，否则会被上个条件排除<br /> {<br /> colornum=x;<br /> return;<br /> }<br /> for (int i=1;i<=x;i++)//判断当前结点着已使用的颜色是否可行<br /> if (ok(k,i))<br /> {//若可行，则设置当前结点颜色，并继续下个节点<br /> color[k]=i;<br /> dfs(k+1,x);<br /> color[k]=0;<br /> return;<br /> }<br /> //考虑另一种情况，即当前结点可以使用已使用的结点，但仍然使用新颜色，则给当前结点分配新的颜色<br /> color[k]=x+1;<br /> dfs(k+1,x+1);<br /> color[k]=0;<br /> }<br /> int main()<br /> {<br /> int o=0;<br /> while (cin>>n && n)<br /> {<br /> o++;<br /> float x[n],y[n];<br /> for (int i=0;i<n;i++)<br /> cin>>x[i]>>y[i];<br /> for (int i=0;i<n;i++)//判断i,j两点距离是否不大于20，若是，则f[i]][j]=true，表示两者相邻，否则为false<br /> for (int j=0;j<n;j++)<br /> if ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=400) f[i][j]=true;<br /> else f[i][j]=false;<br /> memset(color,0,sizeof(color));//初始化color[]，该数组用来记录当前每个节点的颜色<br /> colornum=15;//初始化颜色数，由于最大12个结点，设置15绰绰有余<br /> dfs(0,1);//开始计算<br /> cout<<"The towers in case "<<o<<" can be covered in "<<colornum<<" frequencies."<<endl;<br /> }<br /> return 0;<br /> }<br />