动态字典树+DFS(HDU_1298)

#include <stdio.h>
#include <string.h>

#define MU 26
#define WLEN (100 + 2)

struct node{
    int pr;
    node *child[MU];
    node()
    {
        pr = 0;
        memset(child,NULL,sizeof(child));
    }
};

char findStr[WLEN],temp[WLEN];
char findMap[][5] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int  findPr;

void clear(node *root)
{
    for(int i=0;i<MU;i++)
    {
        if(root->child[i] != NULL)
            clear(root->child[i]);
    }
    delete root;
}

void insert(node *root, char *str, int pr)
{
    node *p = root;
    int len = strlen(str);
    for(int i=0; i<len; i++)
    {
        int k = str[i] - 'a';
        if(p->child[k] == NULL)
        {
            p->child[k] = new node;
        }
        p->child[k]->pr += pr;
        p = p->child[k];
    }
}

void dfs(node *root, char *str, int cur, int n)    //    end n-1
{
    if(cur == n)
    {
        if(root->pr > findPr)
        {
            findPr = root->pr;
            memcpy(findStr,temp,sizeof(findStr));
            findStr[cur] = '';
        }
        return ;
    }

    int curI = str[cur] - '0';
    int len = strlen(findMap[curI]);
    for(int j=0; j<len; j++)
    {
        int k = findMap[curI][j] - 'a';
        if(root->child[k] == NULL)
            continue;
        temp[cur] = findMap[curI][j];
        dfs(root->child[k], str, cur+1, n);
    }
}

void cutFind(node *root, char *str)
{
    int len = strlen(str);
    for(int i=1; i<len; i++)    //len-1 '1';
    {
        findPr = -1;
        dfs(root,str,0,i);
        if(findPr > 0)
            printf("%s
",findStr);
        else
            printf("MANUALLY
");
    }
    printf("
");
}

int main(int argc, char* argv[])
{
#ifdef __MYLOCAL
    freopen("in.txt","r",stdin);
#endif
    
    int __case,t,w,m,i,p;
    char id[WLEN];
    node *root;
    scanf("%d",&t);
    for(__case=1; __case<=t; __case++)
    {
        root = new node;
        scanf("%d",&w);
        for(i=0; i<w; i++)
        {
            scanf("%s %d",id,&p);
            insert(root,id,p);
        }
        printf("Scenario #%d:
",__case);
        scanf("%d",&m);
        for(i=0; i<m; i++)
        {
            scanf("%s",id);
            cutFind(root,id);
        }
        printf("
");
        clear(root);
    }
    
    return 0;
}