package com.data.struct;



public class RelabelToFront {
  private Node[][]graphic;
  private Node s;
  private Node t;
  public RelabelToFront(){
    graphic=new Node[6][6];
    Node node0=new Node();
    node0.start=0;
    node0.end=0;
    graphic[0][0]=node0;
    Node node1=new Node();
    node1.start=1;
    node1.end=1;
    graphic[1][1]=node1;
    Node node2=new Node();
    node2.start=2;
    node2.end=2;
    graphic[2][2]=node2;
    Node node3=new Node();
    node3.start=3;
    node3.end=3;
    graphic[3][3]=node3;
    Node node4=new Node();
    node4.start=4;
    node4.end=4;
    graphic[4][4]=node4;
    Node node5=new Node();
    node5.start=5;
    node5.end=5;
    graphic[5][5]=node5;
    Node node01=new Node();
    node01.c=16;
    node01.start=0;
    node01.end=1;
    graphic[0][1]=node01;
    Node node10=new Node();
    node10.start=1;
    node10.end=0;
    node10.reverse=true;
    graphic[1][0]=node10;
    Node node02=new Node();
    node02.c=13;
    node02.start=0;
    node02.end=2;
    graphic[0][2]=node02;
    Node node20=new Node();
    node20.start=2;
    node20.end=0;
    node20.reverse=true;
    graphic[2][0]=node20;
    Node node13=new Node();
    node13.c=12;
    node13.start=1;
    node13.end=3;
    graphic[1][3]=node13;
    Node node31=new Node();
    node31.start=3;
    node31.end=1;
    node31.reverse=true;
    graphic[3][1]=node31;
    Node node21=new Node();
    node21.c=4;
    node21.start=2;
    node21.end=1;
    graphic[2][1]=node21;
    Node node12=new Node();
    node12.start=1;
    node12.end=2;
    node12.reverse=true;
    graphic[1][2]=node12;
    Node node24=new Node();
    node24.start=2;
    node24.end=4;
    node24.c=14;
    graphic[2][4]=node24;
    Node node42=new Node();
    node42.start=4;
    node42.end=2;
    node42.reverse=true;
    graphic[4][2]=node42;
    Node node32=new Node();
    node32.c=9;
    node32.start=3;
    node32.end=2;
    graphic[3][2]=node32;
    Node node23=new Node();
    node23.start=2;
    node23.end=3;
    node23.reverse=true;
    graphic[2][3]=node23;
    Node node35=new Node();
    node35.c=20;
    node35.start=3;
    node35.end=5;
    graphic[3][5]=node35;
    Node node53=new Node();
    node53.start=5;
    node53.end=3;
    node53.reverse=true;
    graphic[5][3]=node53;
    Node node43=new Node();
    node43.c=7;
    node43.start=4;
    node43.end=3;
    graphic[4][3]=node43;
    Node node34=new Node();
    node34.start=3;
    node34.end=4;
    node34.reverse=true;
    graphic[3][4]=node34;
    Node node45=new Node();
    node45.c=4;
    node45.start=4;
    node45.end=5;
    graphic[4][5]=node45;
    Node node54=new Node();
    node54.start=5;
    node54.end=4;
    node54.reverse=true;
    graphic[5][4]=node54;
    
    s=graphic[0][0];
    t=graphic[5][5];
  }
  
  public void relabelToFront(){
    initializePreflow();
    Node head=graphic[1][1];
    Node last=head;
    for(int i=2;i<graphic.length-1;i++){
      last.lnext=graphic[i][i];
      last=last.lnext;
    }
    for(int i=1;i<graphic.length-1;i++){
      Node lastN=graphic[i][i].N;
      for(int j=0;j<graphic.length;j++){
        if(i==j){
          continue;
        }
        if(lastN==null){
          if(graphic[i][j]!=null){
            Node node=graphic[j][j].clone();
            lastN=node;
            graphic[i][i].N=node;
          }
        }else{
          if(graphic[i][j]!=null){
            Node node=graphic[j][j].clone();
            lastN.next=node;
            lastN=lastN.next;
          }
          
        }
      }
      for(int j=0;j<graphic.length;j++){
        if(i==j){
          continue;
        }
        if(lastN==null){
          if(graphic[j][i]!=null){
            Node node=graphic[j][j].clone();
            lastN=node;
            graphic[i][i].N=node;
          }
        }else{
          if(graphic[j][i]!=null){
            Node node=graphic[j][j].clone();
            lastN.next=node;
            lastN=lastN.next;
          }
          
        }
      }
    }
    for(int i=1;i<graphic.length-1;i++){
      graphic[i][i].current=graphic[i][i].N;
    }
    Node u=head;
    Node prev=u;
    while(u!=null){
      int oldH=u.h;
      discharge(u);
      if(u.h>oldH){
        if(prev!=u){
          prev.lnext=u.lnext;
          u.lnext=head;
          head=u;
        }
      }
      prev=u;
      u=u.lnext;
    }
  }
  
  public void discharge(Node u){
    while(u.e>0){
      Node v=u.current;
      if(v==null){
        relabel(u);
        u.current=u.N;
      }else{
        Node vr=graphic[v.start][v.end];
        if(!graphic[u.start][v.start].reverse&&(graphic[u.start][v.start].c-graphic[u.start][v.start].f>0)&&u.h==vr.h+1){
          push(u,vr);
        }else if(graphic[u.start][v.start].reverse&&graphic[u.start][v.start].f>0&&u.h==vr.h+1){
          push(u,vr);
        }else{
          u.current=v.next;
        }
      }
    }
  }
  
  public void push(Node u,Node v){
    Node uv=graphic[u.start][v.start];
    Node vu=graphic[v.start][u.start];
    int delta=Integer.MAX_VALUE;
    if(!uv.reverse){
      delta=Math.min(delta, Math.min(u.e, uv.c-uv.f));
      uv.f=uv.f+delta;
      vu.f=uv.f;
    }else{
      delta=Math.min(delta, Math.min(u.e, uv.f));
      uv.f=uv.f-delta;
      vu.f=uv.f;
    }
    System.out.println("["+uv.start+","+uv.end+"]:"+delta);
    u.e=u.e-delta;
    v.e=v.e+delta;
    
  }
  public void relabel(Node u){
    int h=Integer.MAX_VALUE;
    for(int i=0;i<graphic.length;i++){
      if(u.start!=i&&graphic[u.start][i]!=null){
        if(!graphic[u.start][i].reverse){
          if(graphic[u.start][i].c-graphic[u.start][i].f>0){
            h=Math.min(h, graphic[i][i].h);
          }
        }else{
          if(graphic[i][u.start].f>0){
            h=Math.min(h, graphic[i][i].h);
          }
        }
      }
    }
    if(h==Integer.MAX_VALUE){
      return;
    }
    u.h=1+h;
    
  }
  public void initializePreflow(){
    s.h=graphic.length;
    for(int i=0;i<graphic.length;i++){
      if(i!=s.start&&graphic[s.start][i]!=null){
        graphic[s.start][i].f=graphic[s.start][i].c;
        graphic[i][s.start].f=graphic[s.start][i].c;
        graphic[i][i].e=graphic[s.start][i].c;
        s.e=s.e-graphic[s.start][i].c;
      }
    }
  }
  
  public void printE(){
    System.out.println("E:");
    for(int i=0;i<graphic.length;i++){
      for(int j=0;j<graphic.length;j++){
        if(graphic[i][j]!=null){
          System.out.print(graphic[i][j].e+" ");
        }else{
          System.out.print("  ");
        }
      }
      System.out.println();
    }
  }
  public void printF(){
    System.out.println("F:");
    for(int i=0;i<graphic.length;i++){
      for(int j=0;j<graphic.length;j++){
        if(graphic[i][j]!=null){
          System.out.print(graphic[i][j].f+" ");
        }else{
          System.out.print("  ");
        }
      }
      System.out.println();
    }
  }
  public void printH(){
    System.out.println("H:");
    for(int i=0;i<graphic.length;i++){
      for(int j=0;j<graphic.length;j++){
        if(graphic[i][j]!=null){
          System.out.print(graphic[i][j].h+" ");
        }else{
          System.out.print("  ");
        }
      }
      System.out.println();
    }
  }
  public void printResult(){
    int result=0;
    for(int i=0;i<graphic.length;i++){
      if(graphic[t.start][i]!=null){
        result+=graphic[i][t.start].f;
      }
    }
    System.out.println("max flow:"+result);
  }
  public void print(){
    for(int i=0;i<graphic.length;i++){
      for(int j=0;j<graphic.length;j++){
        if(graphic[i][j]!=null){
          System.out.print(graphic[i][j].c+" ");
        }else{
          System.out.print("  ");
        }
      }
      System.out.println();
    }
  }
  private class Node{
    private int c;
    private int f;
    private int start;
    private int end;
    private boolean reverse;
    private int e;
    private int h;
    private Node current;
    private Node next;
    private Node N;
    private Node lnext;
    public Node clone(){
      Node newNode=new Node();
      newNode.c=c;
      newNode.f=f;
      newNode.start=start;
      newNode.e=e;
      newNode.end=end;
      newNode.reverse=reverse;
      newNode.h=h;
      return newNode;
    }
  }
  public static void main(String[] args) {
    RelabelToFront r=new RelabelToFront();
    r.print();
    r.relabelToFront();
    r.printResult();

  }

}