fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static int maxn = 100;
  6.     static int bestCost = Integer.MAX_VALUE;
  7.     static int[][] relations = new int[Main.maxn][Main.maxn];
  8.  
  9.     public static void mincut(int N) {
  10.         Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();
  11.         for (int i = 0; i < N; i++) {
  12.             compressed_vertices.add(new Vector<Integer>());
  13.             compressed_vertices.get(i).add(i);
  14.         }
  15.  
  16.         int[] weights;
  17.         weights = new int[N];
  18.         boolean[] exist;
  19.         exist = new boolean[N];
  20.         boolean[] in_A;
  21.         in_A = new boolean[N];
  22.         for (int i = 0; i < N; i++) {
  23.             exist[i] = true;
  24.         }
  25.         for (int ph = 0; ph < N - 1; ++ph) {
  26.             for (int i = 0; i < N; i++) {
  27.                 in_A[i] = false;
  28.             }
  29.             for (int i = 0; i < N; i++) {
  30.                 weights[i] = 0;
  31.             }
  32.             int prev = 0;
  33.             for (int it = 0; it < N - ph; ++it) {
  34.                 int sel = -1;
  35.                 for (int i = 0; i < N; ++i) {
  36.  
  37.                     if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {
  38.                         sel = i;
  39.                     }
  40.                 }
  41.                 if (it == N - ph - 1) {
  42.                     if (weights[sel] < bestCost) {
  43.                         bestCost = weights[sel];
  44.                     }
  45.  
  46.                     compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));
  47.  
  48.                     for (int i = 0; i < N; ++i) {
  49.                         relations[prev][i] = relations[i][prev] += relations[sel][i];
  50.                     }
  51.                     exist[sel] = false;
  52.                 } else {
  53.  
  54.                     in_A[sel] = true;
  55.                     for (int i = 0; i < N; ++i) {
  56.                         weights[i] += relations[sel][i];
  57.                     }
  58.                     prev = sel;
  59.                 }
  60.             }
  61.         }
  62.     }
  63.  
  64.     public static void main(String[] args) {
  65.         Scanner in = new Scanner(System.in);
  66.         int N = in.nextInt();
  67.         int M = in.nextInt();
  68.         for (int i = 0; i < M; i++) {
  69.             int U = in.nextInt() - 1;
  70.             int V = in.nextInt() - 1;
  71.             relations[U][V] = 1;
  72.             relations[V][U] = 1;
  73.         }
  74.         mincut(N);
  75.         System.out.print(bestCost);
  76.     }
  77.  
  78. }
Success #stdin #stdout 0.07s 2184192KB
comments (?)
stdin
copy 
5
5
1 3
1 4 
1 2
2 
3
4 
5
stdout
copy 
1
https://ideone.com/V7DQ4N
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

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!