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(); } }