結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー cho435
提出日時 2025-07-11 22:57:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,122 bytes
コンパイル時間 4,205 ms
コンパイル使用メモリ 256,388 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 22:57:49
合計ジャッジ時間 4,796 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		std::cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

#include <atcoder/all>
void solve() {
	int n;
	cin >> n;
	atcoder::mf_graph<ll> g(410);
	int S = 408, T = 409;
	ll ans = 0;
	rep(i, 0, n) {
		int p;
		cin >> p;
		if (p < 0) {
			g.add_edge(S, i, -p);
		} else {
			ans += p;
			g.add_edge(i, T, p);
		}
	}
	int m;
	cin >> m;
	rep(i, 0, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g.add_edge(u, v, 1e18);
	}
	int k;
	cin >> k;
	rep(i, 0, k) {
		int a, b, s;
		cin >> a >> b >> s;
		a--, b--;
		ans += s;
		g.add_edge(a, n + i, 1e18);
		g.add_edge(b, n + i, 1e18);
		g.add_edge(n + i, T, s);
	}
	ans -= g.flow(S, T);
	cout << ans << "\n";
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0