3323056_ac_844ms_34704k.java

北大大牛代码 1240道题的原代码 超级权威

/*
 * POJ3513
 * DP + HASH
 */

/**
 *
 * @author 20053565
 * @time  Sat Apr 19 01:28:58 CST 2008
 */

import java.util.*;
import java.io.*;

public class Main 
{
    final static int maxn = 20000;
    
    public static void main(String [] args) throws IOException
    {
        new Main().run();
    }
    
    int s, f, cnt;
    TreeMap <String,Integer> tm = new TreeMap <String,Integer> ();
    LinkedList [] map = new LinkedList [maxn];
    
    class Info
    {
        int single, family;
        int stot, ftot;
        int sscnt, sfcnt;
        int ffcnt, fscnt;
    }
    
    Info [] info = new Info [maxn];
    
    public void run()   throws IOException
    {
        BufferedReader in = new BufferedReader ( new InputStreamReader(System.in));
        String line, father;
        StringTokenizer st;
        
        int cas = 1;
        line = in.readLine();
        while(true)
        {    
            st = new StringTokenizer(line);
            s = Integer.parseInt(st.nextToken());
            f = Integer.parseInt(st.nextToken());
            if (s==0&&f==0)
            {
                break;
            }
            tm.clear();
            cnt = 0;
            boolean [] isRoot = new boolean [maxn];
            
            for(int i = 0; i < maxn; i++)
            {
                map[i] = new LinkedList <Integer> ();
            }
            Arrays.fill(isRoot,true);
            while(true)
            {
                line = in.readLine();
                st = new StringTokenizer (line);
                father = st.nextToken();
                if(Character.isDigit(father.charAt(0)))
                {
                    break;
                }
                int fa;
                fa = getId(father);
                while(st.hasMoreTokens())
                {
                    int id = getId(st.nextToken());
                    map[fa].add(id);
                    isRoot[id] = false;
                }
            }
            System.out.print((cas++)+". ");
            int minfee = 0, scnt = 0, fcnt = 0;
            for(int i = 0; i < cnt; i++)
            {
                if(isRoot[i])
                {
                    dfs(i);
                    if(info[i].single < info[i].family || 
                            (info[i].single == info[i].family && info[i].stot < info[i].ftot))
                    {
                        minfee += info[i].single;
                        scnt += info[i].sscnt;
                        fcnt += info[i].sfcnt;
                    }
                    else
                    {
                        minfee += info[i].family;
                        scnt += info[i].fscnt;
                        fcnt += info[i].ffcnt;
                    }
                }
            }
            System.out.println(scnt+" "+fcnt+" "+minfee);
        }
        in.close();
    }
    
    public void dfs(int u)
    {
        info[u] = new Info();
        
        if(map[u].size()==0)
        {
            info[u].stot = 1;
            info[u].ftot = 1;
            info[u].fscnt = 0;info[u].ffcnt = 1;
            info[u].sfcnt = 0;info[u].sscnt = 1;
            info[u].single = s;
            info[u].family = f;
            return ;
        }
        for(int i = 0; i < map[u].size(); i++)
        {
            int v = (Integer)map[u].get(i);
            dfs(v);
        }
        int feesingle, feefamily;
        feesingle = s;
        feefamily = f;
        int stot, ftot, sscnt, ffcnt, sfcnt, fscnt;
        stot = ftot = 1;
        sscnt = ffcnt = 1;
        sfcnt = fscnt = 0;
        //single
        for(int i = 0; i < map[u].size(); i++)
        {
            int  v = (Integer)map[u].get(i);
            if(info[v].single < info[v].family || 
                    (info[v].single == info[v].family && info[v].stot < info[v].ftot))
            {
                feesingle += info[v].single;
                stot += info[v].stot;
                sfcnt += info[v].sfcnt;
                sscnt += info[v].sscnt;
            }
            else
            {
                feesingle += info[v].family;
                stot += info[v].ftot;
                sfcnt += info[v].ffcnt;
                sscnt += info[v].fscnt;
            }
        }
        //family
        for(int i = 0; i < map[u].size(); i++)
        {
            int v = (Integer)map[u].get(i);
            if(info[v].single - s < info[v].family || 
                    (info[v].single - s == info[v].family && info[v].stot - 1 < info[v].ftot))
            {
                feefamily += info[v].single - s;
                ftot += info[v].stot - 1;
                ffcnt += info[v].sfcnt;
                fscnt += info[v].sscnt-1;
            }
            else
            {
                feefamily += info[v].family;
                ftot += info[v].ftot;
                ffcnt += info[v].ffcnt;
                fscnt += info[v].fscnt;
            }
        }
        int len = map[u].size();
        info[u].stot = stot;
        info[u].ftot = ftot;
        info[u].sscnt = sscnt;info[u].sfcnt = sfcnt;
        info[u].ffcnt = ffcnt;info[u].fscnt = fscnt;
        info[u].single = feesingle;
        info[u].family = feefamily;
    }
    
    public int getId(String name)
    {
        if(tm.containsKey(name))
        {
            return tm.get(name);
        }
        else
        {
            tm.put(name, cnt);
            return cnt++;
        }
    }
}