今天做了两个题，上午下午各做了一道，做完题之后开始看书，其中一个题是关于四色定理的题，我感觉这个题很不错，通过做一道题来学习一个新的知识点，那么这道题做的就非常有价值，看书看的是关于弗洛伊德的题和dijkstra算法。
1.四色问题：四色定理就是无论多么错杂的地图，只须要用四种色彩就能将它区分隔来，这四种颜色可以使相邻的面颜色都不相同。 思路大致是这样的：第一个赋值1，第m个面赋值n（n从1开始），循环判断m与1至m-1个面是否相邻，如果相邻且颜色也相同，那么跳出循环，我们就需要对其赋的颜色n++，并且重新开始循环判断。如果m与m-1个面循环判断后没有既相邻又同颜色的，那么m个面可以确定赋值为n。但是如果n到4都没有符合条件，那么我们就需要重新对m-1赋值，它的颜色应该+1，并且继续循环判断m-1。
Channel Allocation问题：这个问题就是用四色定理来解决的。
题目大意： 当一个广播电台在一个非常大的地区，广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而，每个中继器必须慎重选择使用，使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道，那么就不会相互干扰。由于无线电频道是一有限的，一个给定的网络所需的中继频道数目应减至最低。
代码：#include<iostream> #include<cstring> using namespace std; int n,i,j,flag,vis[30],t; char m[30][30]; void dfs(int x); int main() { while(cin>>n) { if(n==0) break; t=n; char s[30]; memset(m,0,sizeof(m)); for(i=0;i<n;i++) { cin>>s; int k=strlen(s); int u=s[0]-'A'+1; if(k>=2) for(int j=2;j<k;j++) { int v; v=s[j]-'A'+1; m[u][v]=1; } } memset(vis,0,sizeof(vis)); flag=0; dfs(1); } return 0; } void dfs(int x) { if(x==t+1) { flag=1; int ma=0; for(i=1;i<=t;i++) if(ma<vis[i]) ma=vis[i]; if(ma==1) cout<<"1 channel needed."<<endl; else cout<<ma<<" channels needed."<<endl; return ; } for(i=1;i<=4;i++) {for(j=1;j<=t;j++) { if(m[x][j]&&vis[j]==i) break;} if(j>t) { vis[x]=i; dfs(x+1); if(flag) return ; vis[x]=0; } } }
解题思路：对这n行逐行搜索，通过四色定理求出共需要多少中继器。
Dijkstra算法：用来计算从一个点到其它所有点的最短路径的算法，只能计算起点是一个点的情况。
注意：不能处理存在负边权的情况。
算法思想：刚开始将所有的点分为两个集合，一个集合1中只有起点，集合2中包含其余的点，然后通过循环，每次循环把集合2中距离最短的点放入集合1中，然后看集合2中的距离是不是可以更改，然后重复此环节，直到集合2中的点全部放入集合1中为止。
