fork download 
  1. public class DancingForever {
  2.  
  3.     boolean[] getMinimalCut(String x)
  4.     {
  5.         int n = 0;
  6.         while(n*n < x.length())
  7.             n++;
  8.         //1
  9.         //2+i
  10.         //2+n+i
  11.         //2+n+n
  12.         int S = 1, T = 2 + n + n;
  13.         networkFlow solver = new networkFlow();
  14.         solver.n = T;
  15.         solver.prepare();
  16.         int INF = 100000000;
  17.  
  18.         for(int i = 0; i < n; i++)
  19.         {
  20.             solver.addedge(S, 2 + i, 1);
  21.             solver.addedge(2+n+i, T, 1);
  22.         }
  23.         for(int i = 0; i < n; i++)
  24.             for(int j = 0; j < n; j++)
  25.                 if(x.charAt(n*i+j) == 'Y')
  26.                 {
  27.                     solver.addedge(2+i, 2+n+j, INF);
  28.                 }
  29.         int flow = solver.maxFlow();
  30.         solver.augment(1, 1000000000);
  31.         boolean[] ret = new boolean[n];
  32.         for(int i = 0; i < n; i++)
  33.             ret[i] = (solver.visited[2+i]);
  34.         return ret;
  35.     }
  36.  
  37.     int[] getMaximalMatching(String x, boolean[] able)
  38.     {
  39.         int n = 0;
  40.         while(n*n < x.length())
  41.             n ++;
  42.         //1
  43.         //2+i
  44.         //2+n+i
  45.         //2+n+n
  46.         int S = 1, T = 2 + n + n;
  47.         networkFlow solver = new networkFlow();
  48.         solver.n = T;
  49.         solver.prepare();
  50.         int INF = 100000000;
  51.         edge[][] edges = new edge[n][n];
  52.         for(int i = 0; i < n; i++)
  53.         {
  54.             solver.addedge(S, 2+i, 1);
  55.             solver.addedge(2+n+i, T, 1);
  56.         }
  57.         for(int i = 0; i < n; i++)
  58.             for(int j = 0; j < n; j++)
  59.                 if(able[i] && x.charAt(n*i+j) == 'Y')
  60.                 {
  61.                     edges[i][j] = solver.addedge(2+i, 2+n+j, 1);
  62.                 }
  63.         int flow = solver.maxFlow();
  64.         int[] ret = new int[flow*2];
  65.         int t = 0;
  66.         for(int i = 0; i < n; i++)
  67.             for(int j = 0; j < n; j++) {
  68.                 if (edges[i][j] != null && edges[i][j].cap == 0) {
  69.                     ret[t] = i;
  70.                     t++;
  71.                     ret[t] = j;
  72.                     t++;
  73.                 }
  74.             }
  75.         return ret;
  76.     }
  77.  
  78.     public int[] getStablePairs(String x)
  79.     {
  80.         int n = 0;
  81.         while(n*n < x.length())
  82.             n ++;
  83.         boolean[] able = new boolean[n];
  84.         for(int i = 0; i < n; i++)
  85.             able[i] = true;
  86.         int[] matching = getMaximalMatching(x, able);
  87.         System.out.println("Maxmatching = " + (matching.length / 2) + " / " + n);
  88.         if(matching.length / 2 == n)
  89.             return matching;
  90.         able = getMinimalCut(x);
  91.  
  92.         matching = getMaximalMatching(x, able);
  93.         return matching;
  94.     }
  95.  
  96.     public class edge
  97.     {
  98.         int dest, cap;
  99.         edge next, pair;
  100.         edge(){dest = 0; cap = 0; next = null; pair = null;}
  101.         edge(int _dest, int _cap, edge _next){dest = _dest; cap = _cap; next = _next; pair = null;}
  102.     };
  103.  
  104.     public class networkFlow
  105.     {
  106.         edge[] e;
  107.         int n, flow;
  108.         int[] pi;
  109.         Boolean[] visited;
  110.  
  111.         void prepare()
  112.         {
  113.             e = new edge[n+1];
  114.             flow = 0;
  115.             pi = new int[n+1];
  116.             visited = new Boolean[n+1];
  117.             for(int i = 1; i <= n; i++)
  118.             {
  119.                 pi[i] = 0;
  120.                 visited[i] = false;
  121.             }
  122.         }
  123.  
  124.         int augment(int w, int limit)
  125.         {
  126.             int t;
  127.             visited[w] = true;
  128.             if(w == n)
  129.             {
  130.                 flow += limit;
  131.                 return limit;
  132.             }
  133.             for(edge i = e[w]; i != null; i = i.next)
  134.             {
  135.                 if(i.cap > 0 && visited[i.dest] == false && pi[w] == pi[i.dest] + 1)
  136.                 {
  137.                     t = augment(i.dest, Math.min(limit, i.cap));
  138.                     if(t > 0)
  139.                     {
  140.                         i.cap -= t;
  141.                         i.pair.cap += t;
  142.                         return t;
  143.                     }
  144.                 }
  145.             }
  146.             return 0;
  147.         }
  148.  
  149.         Boolean fix()
  150.         {
  151.             int t = 1000000000;
  152.             for(int i = 1; i <= n; i++)
  153.                 if(visited[i] == true)
  154.                     for(edge j = e[i]; j != null; j = j.next)
  155.                         if(j.cap > 0 && visited[j.dest] == false)
  156.                             t = Math.min(t, pi[j.dest] + 1 - pi[i]);
  157.             if(t == 1000000000)
  158.                 return false;
  159.             for(int i = 1; i <= n; i++)
  160.                 if(visited[i] == true)
  161.                     pi[i] += t;
  162.             return true;
  163.         }
  164.  
  165.         edge addedge(int s, int t, int c)
  166.         {
  167.             //System.out.println(s + " -> " + t + " : " + c);
  168.             e[s] = new edge(t, c, e[s]);
  169.             e[t] = new edge(s, 0, e[t]);
  170.             e[s].pair = e[t];
  171.             e[t].pair = e[s];
  172.             return e[s];
  173.         }
  174.  
  175.         int maxFlow()
  176.         {
  177.             do
  178.             {
  179.                 do
  180.                 {
  181.                     for(int i = 1; i <= n; i++)
  182.                         visited[i] = false;
  183.                 }
  184.                 while(augment(1, 1000000000) > 0);
  185.             }
  186.             while (fix());
  187.             return flow;
  188.         }
  189.     }
  190.  
  191. }
  192.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
Main.java:1: error: class DancingForever is public, should be declared in a file named DancingForever.java
public class DancingForever {
       ^
1 error
stdout 
Standard output is empty
https://ideone.com/clL4Rk
language:
Java (HotSpot 12)
created:
9 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!