# 題目: UVa 10330 - Power Transmission

# 題目說明

給N個點，M條邊，每個點及邊上有capacity
求此圖的maximum flow

---

INPUT:
第一行輸入一個整數N，接著輸入N個整數，代表點1 ~ N的capacity
輸入一個整數M，接著有M行，每行輸入U、V、C三個整數，代表點U與點V連線，capacity為C
輸入兩個整數B、D

1. 輸入B個整數，代表B與起點相連
2. 輸入D個整數，代表D與終點相連

---

OUTPUT:
輸出maximum flow

# 解題方法

點上的capacity可視為兩個相連的點，連線的capacity為點上的capacity
接著跑Ford Fulkerson演算法，得出maximum flow

# 參考程式碼

#include <iostream>
#include <memory.h>
#include <climits>
#include <queue>

using namespace std;

int N, M, U, V, C, B, D;
int _s = 0, _t;
int G[250][250];
int P[250];
bool vis[250];

void fast_io()
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
}

void init()
{
	memset(G, 0, sizeof(G));
	memset(P, 0, sizeof(P));
}

void read_build()
{
	int a;
	_t = N * 2 + 1;

	for (int i = 1;i <= N; ++i) cin >> G[i][i + N];

	cin >> M;
	while (M--) cin >> U >> V >> C, G[U + N][V] = C;
	
	cin >> B >> D;
	while (B--) cin >> a, G[_s][a] = INT_MAX;
	while (D--) cin >> a, G[a + N][_t] = INT_MAX;
}

int findflow(int u, int v, int c)
{
	if (v == _s) return c;
	c = findflow(P[u], u, min(G[u][v], c));
	G[u][v] -= c;
	G[v][u] += c;
	return c;
}

int maxflow()
{
	int ret = 0;

	while (1)
	{
		memset(vis, false, sizeof(vis));

		queue<int> Q;
		Q.emplace(_s);
		vis[_s] = true;

		while (!Q.empty() && !vis[_t])
		{
			int u = Q.front();
			Q.pop();

			for (int i = 0; i <= _t; ++i) if (!vis[i] && G[u][i] > 0)
			{
				Q.emplace(i);
				vis[i] = true;
				P[i] = u;
			}
		}

		if (!vis[_t]) break;
		ret += findflow(P[_t], _t, INT_MAX);
	}

	return ret;
}

int main()
{
	fast_io();

	while (cin >> N)
	{
		init();
		read_build();
		cout << maxflow() << "\n";
	}
}

# 參考資料

https://www.larrysprognotes.com/UVa-10330/