POJ1129 Channel Allocation

POJ1129 Channel Allocation

題意

給定一個無向圖，用最少的顏色來塗色，使所有相鄰的點顏色都不重復。

思路

數據很小，暴力即可。或者直接貪心(總是選擇能選擇的id最小的顏色)，下面的代碼就是貪心做的。

代碼

#include 
#include 
#include 
using namespace std;
const int maxn = 30;
const int INF = 1000000000;
int cl[maxn];
int n;
int cnt = 1;
bool eg[maxn][maxn];
bool used[maxn];
char s[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n) && n) {
        cnt = 1;
        memset(cl,0,sizeof(cl));
        for(int i = 0 ; i < maxn ; i ++) {
            fill(eg[i],eg[i]+maxn,0);
        }
        for(int i = 0 ; i < n ; i ++) {
            scanf("%s",s);
            for(int j = 2 ; j < strlen(s) ; j ++) {
                eg[s[j]-'A'][i] = eg[i][s[j]-'A'] = true;
            }
        }
        cl[0] = 1;
        for(int i = 1 ; i < n ; i ++) {
            //搜第i個點相鄰的點
            memset(used,false,sizeof(used));
            for(int j = 0 ; j < n ; j ++) {
                if(eg[i][j]) {
                    used[cl[j]] = true;
                }
            }
            //printf("%d\n",used[1]);
            for(int j = 1 ; j < maxn ; j ++) {
                if(!used[j]) {
                    cl[i] = j;
                    if(cnt < j) cnt = j;
                    break;
                }
            }
        }
        //printf("New ");
        //printf("%d %d %d %d\n",cl[0],cl[1],cl[2],cl[3]);
        printf("%d channel",cnt);
        if(cnt > 1) printf("s");
        printf(" needed.\n");
    }
    return 0;
}