Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class minimax {
- FastScanner in;
- PrintWriter out;
- class Kuhn {
- int n;
- boolean[] used;
- int[] left;
- ArrayList<Integer>[] g;
- public Kuhn(ArrayList<Integer>[] g) {
- super();
- this.n = g.length;
- this.g = g;
- used = new boolean[n];
- left = new int[n];
- }
- boolean tryKuhn(int v) {
- if (used[v])
- return false;
- used[v] = true;
- for (int i = 0; i < g[v].size(); ++i) {
- int to = g[v].get(i);
- if (left[to] == -1 || tryKuhn(left[to])) {
- left[to] = v;
- return true;
- }
- }
- return false;
- }
- boolean solve() {
- Arrays.fill(left, -1);
- for (int v = 0; v < n; ++v) {
- Arrays.fill(used, false);
- tryKuhn(v);
- }
- for (int i = 0; i < n; i++)
- if (left[i] == -1)
- return false;
- return true;
- }
- }
- void solve() {
- }
- void run() {
- try {
- in = new FastScanner(new File("minimax.in"));
- out = new PrintWriter(new File("minimax.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- public static void main(String[] args) {
- new minimax().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement