AOJ2033 Rock Man

問題リンク Rock Man

• 概要

N種類のアイテムを全て作りたい。アイテム i を作るにはそれぞれ、day1_iの日数がかかる。アイテム i を作るとき、ある別のアイテムを既に作っていると作業が効率的になるのでday2_iで済むようになる。
全てのアイテムを作るのにかかる最小の日数を求めよ。
N <= 1000
0 < day2 < day1 < 20000

• 解法

アイテムを頂点とし、i→jの辺を、アイテム i を作っているとアイテム j がday2の日数で作れるという関係を表すものとします。すると、どの頂点も入次数1以下、出次数0以上のグラフが出来上がります(ただし、自己ループ辺は除きます)。
day2 < day1という関係が必ず成り立つのでアイテムを作るときはできるだけday2の日数だけかけたいと考えます。なので、方針として、アイテムを何か1つ作ったら、そこからグラフ上で到達できるアイテムをday2のコストで作って行きます。グラフには閉路があるかもしれないので、強連結成分分解してDAGの形にします。DAGにおいて、入次数が0となっている成分は、day1のコストをかけて作ります。その成分の要素数が1個ならば何も迷うことが無いのですが、要素数が2個以上ある場合は(元のグラフで閉路になっていた箇所)その中のどのアイテムを作るかを決めなければなりません。これは、閉路中に登場するアイテムを1つ決め、そのアイテムを作り出すコストと、閉路中の他のアイテムをday2掛けて作るコストの合計が最も小さくなるようなアイテムを見つけます。

• ソース

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

//Rock Man
public class AOJ2033 {

	int n, COUNT, INF = 1<<29, res;
	
	//辺, 逆辺
	List<E>[] edge, rev;
	Map<String, Integer> ref;
	int get(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, COUNT);
		return COUNT++;
	}
	
	class E{
		int t, c;
		public E(int t, int c) {
			this.t = t;
			this.c = c;
		}
	}
	
	boolean[] visited;
	//start SCC
	List<Integer> list;
	void dfs(int k){
		if(visited[k])return;
		visited[k] = true;
		for(E e:edge[k])dfs(e.t);
		list.add(k);
	}
	int[] scc;
	void rdfs(int k, int ID){
		if(visited[k])return;
		visited[k] = true;
		scc[k] = ID;
		for(E e:rev[k])rdfs(e.t, ID);
	}
	//end SCC
	
	//点startから始まる閉路に登場する辺のコストの合計を計算
	int cycle(int k, int start, boolean f){
		if(k==start&&f||rev[k].isEmpty())return 0;
		E e = rev[k].get(0);
		return e.c+cycle(e.t, start, true);
	}
	//アイテムkを作る
	void make(int k){
		for(E e:edge[k]){
			if(visited[e.t])continue;
			res += e.c; visited[e.t] = true; make(e.t);
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			edge = new List[n]; rev = new List[n];
			ref = new HashMap<String, Integer>();
			COUNT = 0;
			for(int i=0;i<n;i++){
				edge[i] = new ArrayList<E>();
				rev[i] = new ArrayList<E>();
			}
			int[] cost = new int[n];
			for(int i=0;i<n;i++){
				int x = get(sc.next());
				cost[x] = sc.nextInt();
				int y = get(sc.next()), c = sc.nextInt();
				if(x==y)continue;
				edge[y].add(new E(x, c)); rev[x].add(new E(y, c));
			}
			visited = new boolean[n];
			list = new ArrayList<Integer>();
			for(int i=0;i<n;i++)if(!visited[i])dfs(i);
			int ID = 0;
			scc = new int[n];
			visited = new boolean[n];
			for(int i=list.size()-1;i>=0;i--){
				int v = list.get(i);
				if(visited[v])continue;
				rdfs(v, ID); ID++;
			}
			int[] deg = new int[ID];
			for(int i=0;i<n;i++)for(E e:edge[i]){
				if(scc[i]!=scc[e.t])deg[scc[e.t]]++;
			}
			res = 0;
			visited = new boolean[n];
			for(int i=0;i<n;i++){
				if(deg[scc[i]]>0||visited[i])continue;
				int p = -1;
				if(rev[i].isEmpty()){
					p = i;
				}
				else{
					int c = cycle(i, i, false);
					p = i;
					int min = c-rev[i].get(0).c+cost[i];
					for(int j=0;j<n;j++){
						if(scc[i]!=scc[j])continue;
						int v = c-rev[j].get(0).c+cost[j];
						if(v<min){
							min = v; p = j;
						}
					}
				}
				visited[p] = true; res+=cost[p];
				make(p);
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2033().run();
	}
}