Sicily---1039. Phone Home（图的最少染色）

题目如下
Description
When relay towers for mobile telephones communicate with the mobile phones in their area, there is always the possibility of interference. So, when assigning the transmission frequency, the FCC makes sure that nearby towers have frequencies that aren’t too close. On the other hand, the FCC does not want to assign too many different frequencies; they want to save as many as possible for other uses. Your job is to find an optimal assignment of frequencies.
In this problem, the frequencies will be integers. Nearby towers must be assigned frequencies that differ by at least 2. You’ll find an assignment using as few frequencies as possible. For example, consider the following two arrangements of towers. Two towers near each other are indicated by the connecting line.

Note that the following are legal frequency assignments to these two tower configurations. However, the second arrangement does not use the fewest number of frequencies possible, since the tower with frequency 5 could have frequency 1.

Input
There will be multiple test cases. Input for each test case will consist of two lines: the first line will contain the integer n, indicating the number of towers. The next line will be of the form x1 y1 x2 y2 … xn yn where xi yi are the coordinates of tower i. A pair of towers are considered “near” each other if the distance between them is no more than 20. There will be no more than 12 towers and no tower will have more than 4 towers near it. A value of n = 0 indicates end of input.

Output
For each test case, you should print one line in the format:

The towers in case n can be covered in f frequencies.

where you determine the value for f. The case numbers, n, will start at 1.

分析：
①题目说塔（即抽象后的节点）的数量最多12 ②要求相邻塔之间频率不能相同，要求最少用几种频率

解决方法：
①节点数量很少，用邻接矩阵存储这个图绰绰有余 ②频率不相同，其实就是图中相邻点染色不同，求最少需要用几种颜色

代码如下：

#include<stack>
#include<iostream>
#include<cmath>
#include<string>
#include<cstdio>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
using namespace std;
const int MAX = 15;//题目说最多只有12个塔
//定义节点，包含坐标信息（x，y）
struct Node
{
double x;
double y;
};
Node nd[MAX];
//定义图结构，以邻接矩阵方式储存，color数组保存的是改点的染色（color == 0 表示没有染过色）
struct Graph
{
int edges[MAX][MAX];
int color[MAX];
}G;
//获得两点之间距离
double dis(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
//将距离小于20的点“连起来”
void connect(int id)
{
for (int i = 1; i < id; i++)
{
double distance = dis(nd[id].x, nd[id].y, nd[i].x, nd[i].y);
if (distance <= 20.01)
G.edges[id][i] = 1, G.edges[i][id] = 1;
}
}
//图的初始化
void initial_graph()
{
memset(G.color, 0, sizeof(G.color));
memset(G.edges, 0, sizeof(G.edges));
}
//获得对图染色的最少颜色
int min_colors(int n)
{
int used[10] = { 0 };//used[i] == 1 表示颜色“i”在邻接点中出现过
int max_color = 0;//当前已用的颜色数量
for (int i = 1; i <= n; i++)
{
memset(used, 0, sizeof(used));
for (int j = 1; j <= n; j++)
{
if (i != j && G.edges[i][j]) //如果节点 j 是节点 i 的邻接点，那么把节点j的颜色标记为used
used[G.color[j]] = 1;
}
for (int k = 1; k <= max_color; k++)//在当前已用的颜色中寻找有没有与 i 的邻接点的颜色不一样的
{
if (!used[k]) //如果找到，就把i标记为这种颜色
{
G.color[i] = k;
break;
}
}
if (!G.color[i])//如果所有已用的颜色都在 i 的邻接点中出现了，那没办法，只能多加一种颜色
max_color += 1, G.color[i] = max_color;
}
return max_color;
}
int main()
{
int n;
int num = 1;
while (cin >> n, n)
{
initial_graph();
memset(nd, 0, sizeof(nd));
for (int i = 1; i < n + 1; i++)
{
cin >> nd[i].x >> nd[i].y;
connect(i);
}
int min_c = min_colors(n);
cout << "The towers in case " << num++ << " can be covered in "<< min_c <<" frequencies." << endl;
}
}

最后

以上就是贪玩保温杯为你收集整理的Sicily---1039. Phone Home（图的最少染色）的全部内容，希望文章能够帮你解决Sicily---1039. Phone Home（图的最少染色）所遇到的程序开发问题。

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