import java.io.BufferedReader;import java.io.File;
import java.io.FileReader;
import java.util.*;
public class HungarianAlgorithm {
static int[][] cost_init;
static int[][] cost_temp;
static int[] selected;
int minRow=-1;
StringBuffer notRows=new StringBuffer("");
int min=9999;
static Vector<String> paths=new Vector<String>();
int numberOfZro=0;//保存独立零元素的个数
public void readData(String filepath) //从文本文件中读取代价矩阵
{
BufferedReader bufread;
String read;
int row=0;
try
{ //得到文本文件的路径
File file=new File(filepath);
FileReader fileread=new FileReader(file);
bufread=new BufferedReader(fileread);
while((read=bufread.readLine())!=null)
{
String[] c=read.toString().substring(1).split(" ");
if(row==0){
int a=Integer.parseInt(c[0]);
cost_init=new int[a][a];
cost_temp=new int[a][a];
selected=new int[a];
}
else{
for(int i=0;i<c.length;i++)
{
cost_init[row-1][i]=Integer.parseInt(c[i]);
cost_temp[row-1][i]=Integer.parseInt(c[i]);
selected[row-1]=-1;
}
}
row++;
}//end while
}catch(Exception d){System.out.println("文件读入出错"+d.getMessage());}
// System.out.println("经过方法readData之后的矩阵为：");
// for(int i=0;i<cost_init.length;i++){
// for(int j=0;j<cost_init.length;j++){
// System.out.print(cost_init[i][j]+" ");
// }
// System.out.println();
// }
}//end readData
public void processFirst(){//每行每列各剪掉本行本列的最小值，得到的新的矩阵保存在cost_temp中
int min=0;
for(int i=0;i<cost_temp.length;i++){//开始对行的计算
min=cost_temp[i][0];
for(int j=0;j<cost_temp.length;j++){
if(cost_temp[i][j]><min) min=cost_temp[i][j];
}//找到本行的最小值
if(min!=0){
for(int j=0;j<cost_temp.length;j++){
cost_temp[i][j]=cost_temp[i][j]-min;
}//找到本行的最小值
}//每个元素减去本行的最小值
}//-----------------------行计算结束
min=0;
for(int j=0;j<cost_temp.length;j++){//开始对行的计算
min=cost_temp[0][j];
for(int i=0;i<cost_temp.length;i++){
if(cost_temp[i][j]><min) min=cost_temp[i][j];
}//找到本列的最小值
if(min!=0){
for(int i=0;i<cost_temp.length;i++){
cost_temp[i][j]=cost_temp[i][j]-min;
}//找到本列的最小值
}//每个元素减去本列的最小值
}//-----------------------行计算结束
// System.out.println("经过方法processFirst处理之后的矩阵为：");
// for(int i=0;i<cost_temp.length;i++){
// for(int j=0;j<cost_temp.length;j++){
// System.out.print(cost_temp[i][j]+" ");
// }
// System.out.println();
// }
}//end precessFirst
public void processSecond(int row){//找到一条独立零元素路径
///-------------------------------------------------无迭代
// for(int i=0;i<cost_temp.length;i++){
// for(int j=0;j<cost_temp.length;j++){
// if(cost_temp[i][j]==0 && judge(j)){
// selected[i]=j;
// break;
// }
// }
// }
// ----------------------------------------------有迭代
for(int j=0;j<cost_temp.length;j++){
selected[row]=-1;
if(cost_temp[row][j]==0 && judge(j)){
selected[row]=j;
if(row!=(cost_temp.length-1)){
processSecond(row+1);
}
}
if(row!=(cost_temp.length-1) && j==(cost_temp.length-1)){
processSecond(row+1);
}
if(row==(cost_temp.length-1) && j==(cost_temp.length-1)){
String path=new String();
for(int i=0;i<selected.length;i++){
// System.out.print(selected[i]+" ");
path=path+String.valueOf(selected[i])+",";
}//for
// System.out.println();
// System.out.println("一次迭代结束，得到的路径条数为："+paths.size());
//-------在插入之前判断selected中非-1的值的个数，如果大于等于当前值就压入，否则不压入
int localNumberOfZro=0;
for(int i=0;i<selected.length;i++){
if(selected[i]!=-1)localNumberOfZro++;
}
if(localNumberOfZro>this.numberOfZro){
System.out.println("清空前，独立零元素的个数为："+this.numberOfZro+",已存的记录条数为："+paths.size());
paths=new Vector<String>();//清空Vector，将这个大的值压入
this.numberOfZro=localNumberOfZro;
paths.add(path);
System.out.println("清空后，独立零元素的个数为："+this.numberOfZro);
}
if(localNumberOfZro==this.numberOfZro){
//判断是否已经有这个元素了，如果有，不加入，没有，则加入
if(ifNotHave(path)){
System.out.println("加入一条记录，现在的总记录数为："+paths.size()+"独立零元素的个数为："+this.numberOfZro);
paths.add(path);//不清空Vector，将这个大的值压入
}
}
}// ifif(row==(cost_temp.length-1) && j==(cost_temp.length-1))
}
}//end processSecond
public boolean ifNotHave(String path){//返回值为真，表示没有包含此条记录
boolean r=true;
for(int i=0;i<paths.size();i++){
if(paths.elementAt(i).equals(path)){
r=false;
break;
}
}
return r;
}
public boolean judge(int colomn){
boolean r=false;
for(int i=0;i<selected.length;i++){
if(selected[i]==colomn){
r=false;
break;
}//if
else if(i==(selected.length-1)){
r=true;
break;
}//else
}//for
return r;
}
public void processT(){//得到未被直线覆盖的元素的最小值
for(int i=0;i<cost_temp.length;i++){
int selectCo=selected[i];
if(selectCo==-1){
notRows.append(i+",");
for(int j=0;j<cost_temp.length;j++){
// System.out.println(cost_temp[i][j]);
if(cost_temp[i][j]><min && judge(j)) {
this.min=cost_temp[i][j];
minRow=i;
}//if
}//for
}// end if(selectCo==-1){
}// for
//---找到未被直线覆盖的最小值
// System.out.println("最小值是"+min+",所在行是："+minRow+"未被直线覆盖的行是"+notRows);
// System.out.println("没减之前的矩阵为：");
// for(int i=0;i<cost_temp.length;i++){
// for(int j=0;j<cost_temp.length;j++){
// System.out.print(cost_temp[i][j]+" ");
// }
// System.out.println();
// }
}
public void sRow(){//未被直线覆盖的行减去最小值
String[] rows=notRows.toString().split(",");
for(int i=0;i<rows.length;i++){
int row=Integer.parseInt(rows[i]);
for(int j=0;j<cost_temp.length;j++){
cost_temp[row][j]=cost_temp[row][j]-this.min;
}
}
// System.out.println("经过方法sRow之后的矩阵为：");
// for(int i=0;i<cost_temp.length;i++){
// for(int j=0;j<cost_temp.length;j++){
// System.out.print(cost_temp[i][j]+" ");
// }
// System.out.println();
// }
}
public void sCol(){//出现负数的列加为0
//找出每列的最小值，如果小于0，给这列加上这个最小值的相反数
for(int j=0;j<cost_temp.length;j++){
int cloMin=999;
for(int i=0;i<cost_temp.length;i++){
if(cost_temp[i][j]><cloMin) cloMin=cost_temp[i][j];
}//找到本列的最小值
if(cloMin><0){
for(int i=0;i<cost_temp.length;i++){
cost_temp[i][j]=cost_temp[i][j]-cloMin;
}//减去本列的最小值
}//if
}//end j
// System.out.println("经过方法sCol之后的矩阵为：");
// for(int i=0;i<cost_temp.length;i++){
// for(int j=0;j<cost_temp.length;j++){
// System.out.print(cost_temp[i][j]+" ");
// }
// System.out.println();
// }
}
public static void main(String[] args) {
HungarianAlgorithm ha=new HungarianAlgorithm();
String filename="C:\\Data\\22C.txt";
ha.readData(filename);
int iteraiton=1;
ha.processFirst();
while(true){
System.out.println("---------------循环次数为-----------------"+iteraiton);
iteraiton++;
ha.numberOfZro=0;
paths=new Vector><String>();
selected=new int[cost_temp.length];
for(int i=0;i<selected.length;i++){
selected[i]=-1;
}
ha.min=9999;
ha.minRow=-1;
ha.notRows=new StringBuffer("");
ha.processSecond(0);
//得到很多条路径，找出-1最少的这一条付给独立矩阵
ha.selectPath();
// System.out.println("独立矩阵");
// for(int i=0;i<selected.length;i++){
// System.out.print(selected[i]+" ");
// }//for
// System.out.println();
System.out.println("独立零元素的个数为"+ha.numberOfZro);
if(ha.numberOfZro><selected.length){
ha.processT();
ha.sRow();
ha.sCol();
}
else{
System.out.println("最终花费代价为："+ha.getCost(selected)+",分配矩阵为：");
// System.out.println("xuzelu______________");
// for(int i=0;i<selected.length;i++){
// System.out.print(selected[i]+" ");
// }//for
// System.out.println();
for(int i=0;i<cost_temp.length;i++){
for(int j=0;j<cost_temp.length;j++){
System.out.print(cost_temp[i][j]+" ");
}//for
System.out.println();
}//for
break;
}//else
}
}
public void selectPath(){
System.out.println("初步选择的路径的条数："+paths.size());
//shuchupaths
for(int i=0;i<paths.size();i++){
System.out.println(paths.elementAt(i));
}
int maxBiao=0;//保存对应的路径的在Vector中的标号返回独立零元素的个数
// 将独立零元素最大的路径付给selectedPath
if(paths.size()!=1){//如果Vector的大小超过1，从中找出对应的代价最大的路径
int cost=0;
for(int i=0;i<paths.size();i++){
String pa=paths.elementAt(i);
int costR=getCost(pa);
if(costR>cost){
maxBiao=i;
}
}// for
}//if
String bestPath=paths.elementAt(maxBiao);
String[] a=bestPath.split(",");
for(int i=0;i<cost_temp.length;i++){
selected[i]=Integer.parseInt(a[i]);
}
}//fangfa
public int getCost(String path){//根据路径，得到这条路径的代价之和
int cost=0;
String[] sel=path.split(",");
for(int i=0;i<cost_init.length;i++){
if(!sel[i].equals("-1")){
cost=cost+cost_init[i][Integer.parseInt(sel[i])];
}
}//for i
return cost;
}
public int getCost(int path[]){//根据路径，得到这条路径的代价之和
int cost=0;
for(int i=0;i<cost_init.length;i++){
if(path[i]!=-1){
cost=cost+cost_init[i][path[i]];
}
}//for i
return cost;
}
}
