acm_code_20053565

/* * 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; System.out.print(new Date()); 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].push(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++; } } }