ABC 091 C 2D Plane 2N Points
解説を見ると、うまく貪欲法でできるらしい。
code:java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[][] blue = new intN2; for (int i = 0; i < N; i++) for (int j = 0; j < 2; j++) redij = scanner.nextInt(); for (int i = 0; i < N; i++) for (int j = 0; j < 2; j++) blueij = scanner.nextInt(); boolean[][] connectivity = new booleanNN; for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (redi0 < bluej0 && redi1 < bluej1) connectivityij = true; }
}
System.out.println(solveFF(N, N, connectivity));
}
private static int solveFF(int N, int M, boolean[][] connectivity) {
int NN = N + M + 2;
int[][] graph = new intNNNN; for (int i = 0; i < N; i++) graph0i + 1 = 1; for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
int[][] flow = new FordFulkerson().solve(NN, graph, 0, NN - 1);
int numPairs = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
return numPairs;
}
private static class FordFulkerson {
public int[][] solve(int N, int[][] graph, int src, int dst) {
int[][] flow = new intNN; int[] path = findPath(N, graph, flow, src, dst);
while (path != null) {
int inc = Integer.MAX_VALUE;
int v = dst;
while (v != src) {
int cf = graphuv - flowuv; if (cf < inc) inc = cf;
v = u;
}
v = dst;
while (v != src) {
v = u;
}
path = findPath(N, graph, flow, src, dst);
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (flowij < 0) flowij = 0; return flow;
}
private int[] findPath(int N, int[][] graph, int[][] flow, int src, int dst) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < N; i++) pathi = -1; queue.add(src);
while (!queue.isEmpty()) {
int from = queue.poll();
if (from == dst) {
return path;
}
for (int to = 0; to < N; to++) {
if (pathto >= 0) continue; queue.add(to);
}
}
}
return null;
}
}
}