Description:

DESA is taking a new project to transfer power. Power is generated by the newly established plant in Barisal. The main aim of this project is to transfer Power in Dhaka. As Dhaka is a megacity with almost 10 million people DESA wants to transfer maximum amount of power through the network. But as always occurs in case of power transmission it is tough to resist loss. So they want to use some regulators whose main aim are to divert power through several outlets without any loss. 　　Each such regulator has different capacity. It means if a regulator gets 100 unit power and it’s capacity is 80 unit then remaining 20 unit power will be lost. Moreover each unidirectional link( Connectors among regulators) has a certain capacity. A link with capacity 20 unit cannot transfer power more than 20 unit. Each regulator can distribute the input power among the outgoing links so that no link capacity is overflown. DESA wants to know the maximum amount of power which can be transmitted throughout the network so that no power loss occurs. That is the job you have to do.

A brief introduction to the problem:

從BARISAL運送能源到DHAKA的路線之中，有若干個調節器(Regulators)與連結(Links)，從BARISAL出來與流進DHAKA的Link容量為無限，其他調節器與連結各有各自的最大乘載能源量，連結為單向輸送，問從BARISAL到DHAKA在這些路徑之中最大的能源輸送量為多少。

Input/Output:

給一整數N為調節器數量，後有N個數字分別為各個調節器的容量，接下來給一整數M，表示調節器之間的Links數量，後M行描述Links的連接狀況與其容量，接著給2整數B和D分別為連接到BARISAL能源站的連結數量與連接到DHAKA的連結數量。後B + D個整數描述與BARISAL和DHAKA兩個地點與調節器的連接情況。B個整數是BARISAL與調節器的鏈結，D個整數是調節器與DHAKA的鏈結。

Output為能源最大輸送量。

Solution:

最大流Maxflow的變形版本，節點也有其容量。解決方法很簡單，將有容量的點拆成兩點，一點輸入一點輸出，中間的鏈結視為調節器的Remaining Capacity，原本指向調節器的鏈結指向輸入端，輸出端指向原本調節器鏈結指向的其他調節器，照此概念建好剩餘網絡之後，再用任意最大流演算法即可求解。

<aside> ✅ 　　Capacity不在Edge反而在Vertex裡面？沒關係，我們把它拆成一條Edge就好了，拆出來的in to out管線也能當作一條輸送管。

</aside>

概念展示圖，中間的兩點是一個調節器拆出來的輸入與輸出端，中間鏈結為Remaining Capacity。

以上述分點概念實現的範例輸入1(題目提供)。

Implementation Code [Accepted]:

小談實作方法，我這次是利用結構表示一個調節器。

struct Regulator {
	int lv = 0; bool vis = 0;
	vector < int >out;
	Regulator(){}
	Regulator(int level, bool visited) {
		lv = level; vis = visited;
	}
	void AddEdge(int to) { out.emplace_back(to); }
};

裡面有Dinic演算法需要用到的level和visited，以及儲存指向其他調節器ID的vector。

unordered_map為圖，內用ID表示各個不同調節器。

Cflows紀錄剩餘容量與反向邊。

pths紀錄DFS用的路徑。