poj-1129-Channel Allocation-四色定理

題意： 給你一個n，代表電台的數量。電台的編號是從A到Z。 然後給你他們之間的鄰接關系，讓你求出最小需要的頻率數。 要求任意兩個相鄰的電台之間不允許用同一頻率。 做法： 由於范圍比較小，所有爆搜都沒關系。但是如果電台的數量比較大的話，就需要運用四色定理了。 四色定理： 對於任意一張地圖，最多只使用四種顏色就可以把地圖任意兩個相鄰的國家染成不同的顏色。 對於這道題目可以看成給電台染色，任意兩個電台用線連起來，任意兩條線都是不相交的，這就符合四色定理。 注意： 注意在需要的頻率為1的時候，channel無s，其他的時候channels有s。 [html]   #include<iostream>   #include<stdio.h>   #include<string.h>   using namespace std;   int main()   {       int i,n,j;       int map[101][101];       char str[1000];       while(scanf("%d%*c",&n)&&n)       {           memset(map,0,sizeof(map));           for(i=1;i<=n;i++)           {               gets(str);               for(j=2;j<strlen(str);j++)               {                   map[i][str[j]-'A'+1]=1;               }           }           int visit[27];           int color[27];           memset(visit,0,sizeof(visit));           memset(color,0,sizeof(color));           int maxlen;           maxlen=0;           for(i=1;i<=n;i++)           {               memset(visit,0,sizeof(visit));               for(j=1;j<=n;j++)               {                   if(map[i][j]!=0)                   {                       if(color[j])                       {                           visit[color[j]]=1;                       }                   }               }               for(j=1;j<=26;j++)               {                   if(visit[j]==0)                   {                       color[i]=j;                       if(j>maxlen)maxlen=j;                       break;                   }               }               if(j==4)break;           }           if(maxlen==1)           {               printf("1 channel needed.\n");           }           else               printf("%d channels needed.\n",maxlen);          }       return 0;      }