Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM 371 ChessMatchup

|  SRM 371 ChessMatchup - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 371 ChessMatchup - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7726

  • ソートしてGreedyで行ける気がするけど安全策をとって最小費用流で。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class ChessMatchup {

// 最小費用流ライブラリは省略

	public int maximumScore(int[] us, int[] them) {
		int len = us.length;
		init(len*2+2);
		int from = len*2;
		int to = len*2+1;
		for (int i = 0 ; i < len ; i++) {
			edge(from, i, 1, 0);
			edge(len+i, to, 1, 0);
		}
		
		int maxscore = 2 * len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (us[i] > them[j]) {
					edge(i, len+j, 1, 0);
				} else if (us[i] < them[j]) {
					edge(i, len+j, 1, 2);
				} else {
					edge(i, len+j, 1, 1);
				}
			}
		}
		return maxscore - min_cost_flow(from, to, len);
	}
}