初学网络流的蒟蒻求支援

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
	chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

struct info{
	int id = 0,to = 0;

	info(int x,int y){id = x;to = y;}
};

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int n,m;
	cin >> n >> m;

	vector<vector<info>> a(n + m + 2);
	vector<int> vct;
	int etop = 0;

	auto edge = [&](int f,int t,int s){
		vct.insert(vct.end(),{s,0});

		a[f].emplace_back(etop++,t);
		a[t].emplace_back(etop++,f);
	};

	int ans = 0;

	for (int i = 1;i <= n;i++){
		int p;
		cin >> p;

		edge(0,i,p);
	}

	for (int i = 1;i <= m;i++){
		int a,b,c;
		cin >> a >> b >> c;

		ans += c;

		edge(a,n + i,INT_MAX);
		edge(b,n + i,INT_MAX);

		edge(n + i,n + m + 1,c);
	}

	vector<int> dis,cur,len(n + m + 2);

	for (int i = 0;i < n + m + 2;i++)
		len[i] = a[i].size();

	auto bfs = [&](){
		dis.assign(n + m + 2,1e9);

		static queue<int> q;
		q.push(0);

		dis[0] = 0;

		for (;!q.empty();){
			int top = q.front();
			q.pop();

			for (auto i:a[top])
				if (vct[i.id]&&dis[i.to] > dis[top] + 1)
					dis[i.to] = dis[top] + 1,q.push(i.to);
		}

		return dis[n + m + 1] != 1e9;
	};

	auto dfs = [&](auto &&self,int x,int y){
		if (x == n + m + 1) return y;

		int ret = 0;

		for (int &iv = cur[x];iv != len[x];iv++){
			auto &i = a[x][iv];

			if (vct[i.id]&&dis[i.to] == dis[x] + 1){
				int f = self(self,i.to,min(y,vct[i.id]));

				y -= f;
				vct[i.id] -= f;
				vct[i.id ^ 1] += f;
				ret += f;

				if (!y) break;
			}
		}

		if (!ret) dis[x] = -1;

		return ret;
	};

	for (;bfs();)
		cur.assign(n + m + 2,0),
		ans -= dfs(dfs,0,INT_MAX);

	cout << ans;
}