poj 2708 Time to Graduate

poj 2708 Time to Graduate

#include <stdio.h>#include <string.h>#define oo 100000bool dfs(int, int);int n,m,mini;bool finished[14];struct CLASS {    char name[8];    int time,preNum;    int prerequisites[13];} subject[15];bool permit(int num) {    int i;    for(i=0; i<subject[num].preNum && finished[subject[num].prerequisites[i]]; i++);    if(i == subject[num].preNum) return true;    return false;}bool selectAndDfs(int total, int elect, int from, int que[], int result[], int lev, int semester) {    int i;    if(total-from < elect) return false;    if(from == total && elect == 0) {        for(i=0; i<m; i++) finished[result[i]] = true;        dfs(lev+m, semester+1);        for(i=0; i<m; i++) finished[result[i]] = false;        return true;    }    for(i=from; i<total; i++) {        result[m-elect] = que[i];        selectAndDfs(total, elect-1, i+1, que, result, lev, semester);    }    return true;}bool dfs(int lev, int semester) {    if(semester-1 >= mini) return false;    if(lev == n) {        if(semester-1 < mini) mini = semester-1;        return true;    }    int i,tn=0,que[15];    for(i=0; i<n; i++) if(!finished[i] && permit(i) && (subject[i].time & (1<<semester%2)) != 0) que[tn++] = i;    if(tn <= m) {        for(i=0; i<tn; i++) finished[que[i]] = true;        dfs(lev+tn,semester+1);        for(i=0; i<tn; i++) finished[que[i]] = false;    }    else {        int temp[15];        selectAndDfs(tn,m,0,que,temp,lev,semester);    }    return false;}int main() {    while(scanf("%d%d", &n, &m) == 2 && !(n == -1 && m == -1)) {        int i,j,k,p,t;        for(i=0; i<n; i++) { scanf("%s", &subject[i].name); subject[i].time = subject[i].preNum = 0;        }        for(i=0; i<n; i++) { char s[10]; scanf("%s", s); for(j=0; j<n && strcmp(s, subject[j].name) != 0; j++); scanf("%s", s); if(s[0] == 'B') subject[j].time = 3; else if(s[0] == 'S') subject[j].time = 1; else subject[j].time = 2; scanf("%d", &t); for(k=0; k<t; k++) {     scanf("%s", s);     for(p=0; p<n && strcmp(s, subject[p].name) != 0; p++);     subject[j].prerequisites[subject[j].preNum++] = p; }        }        memset(finished, 0, sizeof(finished));        mini = oo;        dfs(0,1);        printf("The minimum number of semesters required to graduate is %d.n", mini);    }    return 0;}