poj1129:http://poj.org/problem?id=1129
题意：给你一个图，然后求图的最小的顶点着色情况。
题解：可以采用近似有效算法。对于一个顶点，检查与他相邻的顶点的着色情况，如果对于当前的,这种颜色，她相邻的顶点没有着上，那么这个点就可以染上这种颜色，否则把当前的颜色加1，然后重新检查直到满足为止.最后统计一下一共然后多少种颜色即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int color[27];//记录颜色的使用情况，每个点的着色情况 int map[27][27];//储存图 int n,c;//点的个数，一个颜色总类 char ss[200];//处理读入 int solve(){ c=1; memset(color,0,sizeof(color)); for(int i=1;i<=n;i++){ c=1;//对于每个点都要从1开始检查， bool flag=false; for(int j=1;j<=n;j++) if(map[i][j]&&color[j]==c){//只要当前的点相邻有着上了一种颜色，那么这个点就不能染这种颜色 flag=true; c++; } while(flag){//检查，直到它相邻的点都没有染上这种颜色 flag=false; for(int j=1;j<=n;j++) if(map[i][j]&&color[j]==c){ flag=true; c++; } } color[i]=c;//给当前的点着上这种颜色 } return c; } int main(){ while(~scanf("%d",&n)&&n){ memset(map,0,sizeof(map)); for(int i=1;i<=n;i++){ scanf("%s",ss); int len=strlen(ss); for(int j=2;j<len;j++){ int v=ss[j]-‘A‘+1; map[i][v]=map[v][i]=1; } } solve(); bool used[27]; memset(used,0,sizeof(used)); int counts=0; for(int i=1;i<=n;i++){ if(!used[color[i]]&&color[i]){//统计一共有多少中颜色 counts++; used[color[i]]=true; } } if(counts==1) printf("%d channel needed.\n",counts); else printf("%d channels needed.\n",counts); } }