2D Plane 2N Points
https://beta.atcoder.jp/contests/abc091/tasks/arc092_a
二部マッチング問題です。
AOJの二部マッチングの問題と内容的には殆ど同じです。
二部マッチング問題
AOJの二部マッチングの問題を解くことができればこの問題も同じようにして解くことができます。下の記事でその解答を載せています。
二部マッチング
二部グラフの最大マッチング問題です。グラフ系の問題は苦手というよりも、知識がほとんど無いので、問題と解答をセットで...
yamakasa.net
2018-10-29 16:01
考え方
隣接リストの部分は自分で作らないといけません。赤い点と青い点がそれぞれ \( N \) 個あるので、赤い点にそれぞれ \( 0 \) から \( N – 1 \) までの番号を振り、青い点にそれぞれ \( N \) から \( 2N – 1 \) までの番号を振ります。
赤い点 \( i \) と青い点 \( j \) に辺が張られる条件は、
\[ a_i < c_j \ \& \ b_i < d_j\]
です。このとき、\( (i, j) \) の辺ができます。これを全ての \( i, j \) について調べます。
あとは、最大マッチングを求めるアルゴリズムに投げます。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class ProblemC { static int V; static int []match; static boolean []used; static Map<Integer, List<Integer>> G = new HashMap<Integer, List<Integer>>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[]a = new int[N]; int[]b = new int[N]; int[]c = new int[N]; int[]d = new int[N]; for(int i = 0; i < N; i++) { a[i] = sc.nextInt(); b[i] = sc.nextInt(); } for(int i = 0; i < N; i++) { c[i] = sc.nextInt(); d[i] = sc.nextInt(); } sc.close(); V = 2 * N; match = new int[V]; used = new boolean[V]; // 隣接リストを作成 for(int i = 0; i < N; i++) { List<Integer> list1 = new ArrayList<Integer>(); for(int j = 0; j < N; j++) { if(a[i] < c[j] && b[i] < d[j]) { list1.add(N + j); if(G.containsKey(N + j)) { G.get(N + j).add(i); }else { List<Integer> list2 = new ArrayList<Integer>(); list2.add(i); G.put(N + j, list2); } } } G.put(i, list1); } int max = bipatricleMatching(); System.out.println(max); } static boolean dfs(int v) { used[v] = true; if(!G.containsKey(v)) return false; for(int i = 0; i < G.get(v).size(); i++) { int u = G.get(v).get(i); int w = match[u]; if(w < 0 || (!used[w] && dfs(w))) { match[v] = u; match[u] = v; return true; } } return false; } static int bipatricleMatching() { int res = 0; Arrays.fill(match, -1); for(int v = 0; v < V; v++) { if(match[v] < 0) { Arrays.fill(used, false); if(dfs(v)) res++; } } return res; } } |
感想
この問題を解くためにAOJの問題を先に解いていました。解説では最大マッチングのアルゴリズムを使わなくても解けるそうなので、そちらの方も学ぶ必要がありますね。
ネットワーク系の問題は実際に手を動かして勉強する必要があるんですが、適切な教材がないので、アルゴリズムの活用だけにとどまっています。いつかはちゃんと勉強したいと思っています。