Network Max Flow

Ford-Fulkerson Algorithm

  1. 使用bfs尋找最短路徑
  2. 求此路徑最小能通過的水管口徑min_val
  3. 把此路徑中每個節點能用的流量減掉min_val
  4. 把反路徑中每個節點能用的流量加上min_val
  5. 重複以上步驟直到找不到新的路徑

記錄反路徑的原因是要讓此水管的水能被重新分配,假設a b兩端,已有a流向b的水5單位,現以b當作目前所在的位置,如果想要從b流向a 2單位,那就等於在a端從原來的5單位分配2單位給當前路徑,就可以繼續流了,而b端則由(當前的水2單位)+(原有的5單位-分配出去的2單位=3單位)=5單位,還是5單位,代表此操作並不會改變之前的結果

還有一個關鍵就是找最短路徑

模板題

















































int rest[MAXN][MAXN],pre[MAXN],mi[MAXN];

bool bfs(int s){
	queue<int> q;
	memset(pre,-1,sizeof(pre));   //初始化為未走過
	
	q.push(s);
	pre[s]=s;  //起點標記為走過
	mi[s]=inf;  //起點能用的網路流量初始為最大(為了求最小值)
	
	while(!q.empty()){
		int now=q.front();q.pop();
		
		for(int i=1;i<=n;i++){
			if(pre[i]==-1 && rest[now][i]){  //如果沒走過i且從now走到i的路還有流量
				pre[i]=now;  //記錄從哪裡來,以用來走inverse
				mi[i]=min(mi[now],rest[now][i]);  //記錄每條路徑的最小值
				
				if(i==n) return true;  //如果走到終點就直接回傳,求最短路徑
				q.push(i);
			}
		}
	}
	return false;  //走不到end point
}

int max_flow(){
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		rest[u][v]+=w;  //流量可累計
	}
	int sum_flow=0;
	while(bfs(1)){
		int increase_flow=mi[n];
		sum_flow+=increase_flow;
		
		int now=n;
		while(now!=1){
			rest[pre[now]][now]-=increase_flow;  //減少還能用的流量
			rest[now][pre[now]]+=increase_flow;  //應加inverse流量
			now=pre[now];  //回朔
		}
	}
	return sum_flow;
}

分割問題

求刪除最少數量的邊能讓1不能走到N

想法:先討論要刪除幾條邊，每次bfs找能從1走到N的一條路徑，並把它標示成走過，接著找下一條路徑直到找不到為止，這就是上面的最大流演算法，只要每一條邊視權重為1即可，這樣要刪除的邊的個數就是最大流的答案，那要刪除哪條邊呢?可視為左邊中間右邊，左半邊包含起點(1)，右半邊包含終點(N)，注意到中間連接的部分，每條邊一定都被標示為走過，如果沒被標示過那上面在做最大流bfs的時候就還會找到增廣路徑，所以不合法，可以把中間部分想像成腰帶，束緊了連接左右兩邊的邊，在刪除的時候要刪除這些邊即可，我們可以從1節點dfs一次可走到的節點，因為有反向流，在左半邊的任何節點都會被遍歷到，右半邊任何節點都不會被遍歷到，因為反向流堵住了中間部分，讓dfs走不過去，遍歷完後，找節點i被走過 節點j沒被走過且(i,j)之間有邊的兩個點，此邊即為答案










cout << sum_flow << '\n';
dfs(1);
for(int i=1;i<=n;i++){
    if(vis[i]){
        for(int j=1;j<=n;j++){
            if(!vis[j] && has_edge[i][j]) cout << i << ' ' << j << '\n';
        }
    }
}
Select a repo