channel allocation.txt

来自「以前ACM在哈工程HRBEU做的一些简单题目」· 文本 代码 · 共 53 行

#include <iostream>   
#include <stdio.h>   
using namespace std;   
const int MAXN = 30;   
int n, ok, c[MAXN], data[MAXN][MAXN];   
int check(int x){   
    for (int i = 1; i <= n; ++i){   
        if (data[x][i]==1&&c[x]==c[i])   
        return 0;   
    }   
    return 1;   
}   
void search(int id, int color){   
    if (id == n + 1){   
        ok = 1; return;   
    }   
    if (ok) return;   
    for (int i = 1; i != color + 1; ++i){   
        c[id] = i;   
        if (check(id)) search(id + 1, color);   
    }   
    c[id] = 0;   
}   
int main(){   
    char ch, tch;   
    int x, y;   
    while (cin >> n && n != 0){   
        tch = getchar();   
        memset(data, 0, sizeof(data));   
        for (int i = 0; i != n; ++i){   
            ch = getchar();   
            x = ch - 'A' + 1;   
            tch = getchar();   
            while (ch = getchar()){   
                if (ch < 'A') break;   
                y = ch - 'A' + 1;   
                data[x][y] = data[y][x] = 1;   
            }   
        }   
        ok = 0;
        for (int i = 1; i <= n; ++i){   
            memset(c, 0, sizeof(c));   
             search(1, i);   
            if (ok){   
                if (i == 1) cout << "1 channel needed." << endl; 
                else cout << i << " channels needed." << endl;   
                break;   
            }   
        }   
    }   
    return 0;   
}