fork download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.StreamTokenizer;
  6. import java.util.ArrayList;
  7. import java.util.Collections;
  8. import java.util.Iterator;
  9. import java.util.TreeSet;
  10. import java.lang.Integer;
  11. import java.util.Stack;
  12.  
  13. public class flow_kp_java {
  14.  
  15.     static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  16.  
  17.     static int nextInt() {
  18.         try {
  19.             st.nextToken();
  20.             return (int) st.nval;
  21.         } catch (IOException ex) {
  22.             return 0;
  23.         }
  24.     }
  25.  
  26.     static double nextDouble() {
  27.         try {
  28.             st.nextToken();
  29.             return st.nval;
  30.         } catch (IOException ex) {
  31.             return 0;
  32.         }
  33.     }
  34.  
  35.     static class Edge {
  36.  
  37.         int b, c, d, i;
  38.  
  39.         public Edge(int b, int c, int d, int i) {
  40.             this.b = b;
  41.             this.c = c;
  42.             this.d = d;
  43.             this.i = i;
  44.         }
  45.     }
  46.  
  47.     public static void main(String[] args) {
  48.         int n = nextInt();
  49.         int m = nextInt();
  50.  
  51.         ArrayList<ArrayList<Edge>> inc = new ArrayList<ArrayList<Edge>>();
  52.         for (int i = 0; i <= n; i++) {
  53.             inc.add(new ArrayList<Edge>());
  54.         }
  55.  
  56.         int[] half = new int[200001];
  57.         int[] current = new int[200001];
  58.         boolean[] visited = new boolean[200001];
  59.  
  60.         int[] direction = new int[200005];
  61.  
  62.         Stack<Integer> q = new Stack<Integer>();
  63.  
  64.  
  65.         int a, b, c;
  66.         for (int i = 0; i < m; i++) {
  67.             a = nextInt();
  68.             b = nextInt();
  69.             c = nextInt();
  70.             inc.get(a).add(new Edge(b, c, 0, i));
  71.             inc.get(b).add(new Edge(a, c, 1, i));
  72.             current[a] += c;
  73.             current[b] += c;
  74.         }
  75.         for (int i = 0; i < n; i++) {
  76.             half[i] = current[i] / 2;
  77.         }
  78.         visited[1] = true;
  79.         q.push(1);
  80.         while (!q.empty()) {
  81.             int next = q.pop();
  82.             for (Edge e : inc.get(next)) {
  83.                 if (!visited[e.b]) {
  84.                     direction[e.i] = e.d;
  85.                     current[e.b] -= e.c;
  86.                     if (current[e.b] == half[e.b] && e.b != n) {
  87.                         visited[e.b] = true;
  88.                         q.push(e.b);
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.         for (int i = 0; i < m; i++) {
  94.             System.out.println(direction[i]);
  95.         }
  96.     }
  97. }
  98.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qE3vYO
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!