Next Spaceship

Driving into future…

POJ 1129 Channel Allocation Report

| Comments

View this problem on POJ: 1129 Channel Allocation This problem involves the following knowledge:

  • Four color theorem
  • DFS (Depth First Search)

Any Greedy Method is wrong. The test cases on POJ are so weak that some greedy methods can also be accepted.

Try this test case if you don’t believe your greedy method is wrong:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
6
A:BEF
B:AC
C:BD
D:CEF
E:ADF
F:ADE
0

Don’t view my source code:

POJ 1129 Channel Allocation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <memory>
#include <cstring>
#include <algorithm>
using namespace std;
bool b[26][26];
char a[26];
int n,m;
void dfs(int d){
    int i,j;
    if(d==n){
        int mm=*max_element(a,a+n);
        if(mm<m)m=mm;
        return;
    }
    for(i=1;i<5;i++){
        bool ok=true;
        a[d]=i;
        for(j=0;j<n;j++){
            if(b[d][j]&&a[d]==a[j]&&d!=j){
                ok=false;
                break;
            }
        }
        if(ok){
            dfs(d+1);
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF&&n){
        char d[26];
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        m=4;
        int i,j;
        for(i=0;i<n;i++){
            scanf("%s",d);
            for(j=2;j<strlen(d);j++){
                b[i][d[j]-'A']=1;
                b[d[j]-'A'][i]=1;
            }
        }
        dfs(0);
        if(m==1)
            printf("1 channel needed.\n");
        else
            printf("%d channels needed.\n",m);
    }
    return 0;
}

Comments