Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 29th, 2020 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.ArrayDeque;
  3. import java.util.Arrays;
  4. import java.util.StringTokenizer;
  5.  
  6. public class CountingStar {
  7.     static class FastScanner {
  8.         BufferedReader br;
  9.         StringTokenizer st;
  10.  
  11.         public FastScanner() {
  12.             br = new BufferedReader(new InputStreamReader(System.in));
  13.         }
  14.  
  15.         String next() {
  16.             while (st == null || !st.hasMoreElements()) {
  17.                 try {
  18.                     st = new StringTokenizer(br.readLine());
  19.                 } catch (IOException e) {
  20.                     e.printStackTrace();
  21.                 }
  22.             }
  23.             return st.nextToken();
  24.         }
  25.  
  26.         int nextInt() {
  27.             return Integer.parseInt(next());
  28.         }
  29.  
  30.         long nextLong() {
  31.             return Long.parseLong(next());
  32.         }
  33.     }
  34.  
  35.     static class DirectedEdge {
  36.         int from;
  37.         int to;
  38.         int c;
  39.         int flow;
  40.         DirectedEdge reversedEdge;
  41.         boolean visited = false;
  42.  
  43.         public DirectedEdge(int from, int to, int c) {
  44.             this.from = from;
  45.             this.to = to;
  46.             this.c = c;
  47.             this.flow = 0;
  48.             reversedEdge = null;
  49.         }
  50.     }
  51.  
  52.     static class Query {
  53.         int a;
  54.  
  55.  
  56.         int b;
  57.  
  58.         public Query(int a, int b, int c) {
  59.             this.a = a;
  60.             this.b = b;
  61.             this.c = c;
  62.         }
  63.  
  64.         int c;
  65.  
  66.     }
  67.  
  68.     static class Ship {
  69.         int number;
  70.  
  71.         public Ship(int number, int to) {
  72.             this.number = number;
  73.             this.to = to;
  74.         }
  75.  
  76.         int to;
  77.     }
  78.  
  79.     public static void main(String[] args) {
  80.         FastScanner scanner = new FastScanner();
  81.         int n = scanner.nextInt();
  82.         int m = scanner.nextInt();
  83.         int k = scanner.nextInt();
  84.         int source1 = scanner.nextInt() - 1;
  85.         int sink1 = scanner.nextInt() - 1;
  86.         ArrayDeque<Integer>[] to1 = new ArrayDeque[n];
  87.         for (int i = 0; i < n; i++) {
  88.             to1[i] = new ArrayDeque<>();
  89.         }
  90.         for (int i = 0; i < m; i++) {
  91.             int a = scanner.nextInt() - 1;
  92.             int b = scanner.nextInt() - 1;
  93.             to1[a].addLast(b);
  94.             to1[b].addLast(a);
  95.         }
  96.         int L = shortestPath(to1, source1, sink1);
  97.         ArrayDeque<Query> queries = new ArrayDeque<>();
  98.  
  99.         for (int i = 0; i < (L + k - 1); i++) {
  100.             for (int j = 0; j < n; j++) {
  101.                 queries.addLast(new Query(i * n + j, (i + 1) * n + j, Integer.MAX_VALUE));
  102.                 for (int to : to1[j]
  103.                 ) {
  104.                     queries.addLast(new Query(i * n + j, (i + 1) * n + to, 1));
  105.                 }
  106.             }
  107.             int level = i + 1;
  108.             if (level >= L) {
  109.                 int source = source1;
  110.                 int sink = level * n + sink1;
  111.                 ArrayDeque<DirectedEdge>[] to = new ArrayDeque[level * n + n];
  112.                 for (int j = 0; j < to.length; j++) {
  113.                     to[j] = new ArrayDeque<>();
  114.                 }
  115.                 for (Query query : queries) {
  116.                     int a = query.a;
  117.                     int b = query.b;
  118.                     int c = query.c;
  119.                     DirectedEdge edge1 = new DirectedEdge(a, b, c);
  120.                     DirectedEdge reversedEdge1 = new DirectedEdge(b, a, 0);
  121.                     edge1.reversedEdge = reversedEdge1;
  122.                     reversedEdge1.reversedEdge = edge1;
  123.                     to[a].addLast(edge1);
  124.                     to[b].addLast(reversedEdge1);
  125.                 }
  126.                 boolean[] mark = new boolean[to.length];
  127.                 int maxFlow = 0;
  128.                 while (true) {
  129.                     Arrays.fill(mark, false);
  130.                     int delta = dfs(source, Integer.MAX_VALUE, mark, to, sink);
  131.                     if (delta > 0) {
  132.                         maxFlow += delta;
  133.                         if (maxFlow >= k) break;
  134.                     } else {
  135.                         break;
  136.                     }
  137.                 }
  138.                 if (maxFlow >= k) {
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top