packagecom.liuzhen.practice;importjava.util.ArrayList;importjava.util.Scanner;public classMain {public static int MAX = 1000;public static int n; //圖中頂點數目
public static boolean[] used = new boolean[MAX]; //判斷頂點是否在隊列中
public static int[] pre = new int[MAX]; //記錄最短增廣路徑中相應節點的前節點
public static int[] distance = new int[MAX]; //記錄源點到圖中其他所有頂點的最短距離
public static int[] capacity = new int[MAX]; //用于記錄周遊圖每一次得到增廣路徑的流量
public static ArrayList[] map; //圖的鄰接表//表示圖中邊資訊内部類
static classedge {public int from; //邊的起點
public int to; //邊的終點
public int cap; //邊的容量
public int cost; //邊的費用
public edge(int from, int to, int cap, intcost) {this.from =from;this.to =to;this.cap =cap;this.cost =cost;
}
}//輸入給定圖資料
@SuppressWarnings("unchecked")public voidinit() {
Scanner in= newScanner(System.in);
n=in.nextInt();int k = in.nextInt(); //給定圖的邊數目
map = newArrayList[n];for(int i = 0;i < n;i++)
map[i]= new ArrayList();for(int i = 0;i < k;i++) {int from =in.nextInt();int to =in.nextInt();int cap =in.nextInt();int cost =in.nextInt();
map[from].add(new edge(from, to, cap, cost)); //正向邊
map[to].add(new edge(to, from, 0, -cost)); //反向邊
}
}//尋找頂點start到頂點end的最短路徑(PS：即費用最少的一條增廣路徑)
public boolean spfa(int start, intend) {int[] count = new int[n];for(int i = 0;i < n;i++) {
used[i]= false;
pre[i]= -1;
distance[i]=Integer.MAX_VALUE;
capacity[i]=Integer.MAX_VALUE;
}
used[start]= true;
pre[start]=start;
distance[start]= 0;
count[start]++;
ArrayList list = new ArrayList();
list.add(start);while(!list.isEmpty()) {int index = list.get(0);
list.remove(0);
used[index]= false;for(int i = 0;i < map[index].size();i++) {
edge temp=map[index].get(i);if(temp.cap > 0 && distance[temp.to] > distance[index] +temp.cost) {//記錄頂點start到圖中其它頂點之間的最短費用距離
distance[temp.to] = distance[index] +temp.cost;
pre[temp.to]=index;//記錄增廣路徑能夠流通的最大流量
capacity[temp.to] =Math.min(capacity[index], temp.cap);if(!used[temp.to]) {
used[temp.to]= true;
list.add(temp.to);
count[temp.to]++;if(count[temp.to] > n) //用于判斷圖中是否有負環
return false;
}
}
}
}if(distance[end] != Integer.MAX_VALUE && pre[end] != -1)return true;return false;
}public intgetResult() {
init();//輸入給定圖資料
int minCost = 0;int start = 0; //把源點設定為頂點0
int end = n - 1; //把彙點設定為頂點n - 1
while(true) {if(spfa(start, end) == false)break;
System.out.println("增廣路徑增量："+capacity[end]+", 費用流："+distance[end]);
minCost+= distance[end] *capacity[end];int last =end;int begin =end;
System.out.print("彙點出發");while(begin !=start) {
last=begin;
begin=pre[last];int i = 0, j = 0;
System.out.print("——>"+last);for(;i < map[begin].size();i++) {if(map[begin].get(i).to ==last)break;
}
map[begin].get(i).cap-= capacity[end]; //正向邊剩餘流量減少
for(;j < map[last].size();j++) {if(map[last].get(j).to ==begin)break;
}
map[last].get(j).cap+= capacity[end]; //反向邊剩餘流量增加
}
System.out.println("——>"+begin);
}returnminCost;
}public static voidmain(String[] args) {
Main test= newMain();int result =test.getResult();
System.out.println(result);
}
}