TIOJ 1491 G.丁丁共和國 ( NPSC 2007 )

 poao899    580K    15MS    G++     1.41K     2009-11-13 15:45:31                                 .


字串處理 + 最遠距離點對


唔順便練一下map XD  比想像中的好用太多了orz



之前寫過兩次DFS這次改寫樹型DP


//******************************

//1491
//Tree DP + map

#include<stdio.h>
#include<map>
#include<string.h>
struct name{
    char n[200];
    bool operator<(const name &b)const{
        return strcmp(n,b.n)>0;
    }
}c1,c2;
struct edge{
    int i,j;
    edge *next;
}E[6000],*V[3000];
int eCnt;
void set(int i,int j){
    edge *p;
    E[eCnt].i=i;
    E[eCnt].j=j;
    p=V[i];
    V[i]=&E[eCnt];
    E[eCnt].next=p;
    eCnt++;
    E[eCnt].i=j;
    E[eCnt].j=i;
    p=V[j];
    V[j]=&E[eCnt];
    E[eCnt].next=p;
    eCnt++;
}
int DP[3000];
int k,n,cnt,maxLen;
bool visited[3000];
int treeDP(int now){
    visited[now]=1;
    if(!DP[now]){
        int max=0,max2=0,n;
        edge *p=V[now];
        while(p!=NULL){
            if(visited[p->j]==0){
                //printf("now%d son %d\n",now,p->j);
                n=treeDP(p->j)+1;
                if(n>max){
                    max2=max;
                    max=n;
                }
                else if(n>max2){
                    max2=n;
                }
            }
            p=p->next;
        }
        maxLen>?=max+max2;
        DP[now]=max;
        //printf("DP%d %d\n",now,DP[now]);
    }
    return DP[now];
}
main(){
    scanf("%d",&k);
    while(k--){
        //Initialize
        std::map<name,int> city;
        scanf("%d",&n);
        maxLen=0;
        for(int i=0;i<3000;i++){
            DP[i]=0;
            V[i]=NULL;
            visited[i]=0;
        }
        eCnt=0;
        cnt=1;
        //Input
        while(1){
            scanf("%s%s",c1.n,c2.n);
            if(!strcmp(c1.n,"=") && !strcmp(c2.n,"="))break;
            int n1=city[c1],n2=city[c2];
            if(n1==0)n1=city[c1]=cnt++;
            if(n2==0)n2=city[c2]=cnt++;
            set(n1,n2);
        }
        treeDP(1);
        printf("%d\n",maxLen);
    }
}