結果
| 問題 |
No.3201 Corporate Synergy
|
| コンテスト | |
| ユーザー |
 umimel
|
| 提出日時 | 2025-07-11 23:19:31 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 6,344 bytes |
| コンパイル時間 | 2,484 ms |
| コンパイル使用メモリ | 178,504 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-07-11 23:19:35 |
| 合計ジャッジ時間 | 3,680 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;
struct union_find{
vector<int> par;
vector<int> siz;
union_find(int n) : par(n), siz(n, 1){
for(int i=0; i<n; i++) par[i] = i;
}
int root(int x){
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y){
int rx = root(x);
int ry = root(y);
if (rx == ry) return;
if (siz[rx] < siz[ry]) swap(rx, ry);
siz[rx] += siz[ry];
par[ry] = rx;
}
bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}
int size(int x){
return siz[root(x)];
}
};
template<typename T>
struct edge{
int from;
int to;
T cost;
int id;
edge(){}
edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}
void reverse(){swap(from, to);}
};
template<typename T>
struct edges : std::vector<edge<T>>{
void sort(){
std::sort(
(*this).begin(),
(*this).end(),
[](const edge<T>& a, const edge<T>& b){
return a.cost < b.cost;
}
);
}
};
template<typename T = bool>
struct graph : std::vector<edges<T>>{
private:
int n = 0;
int m = 0;
edges<T> es;
bool dir;
public:
graph(int n, bool dir) : n(n), dir(dir){
(*this).resize(n);
}
void add_edge(int from, int to, T cost=1){
if(dir){
es.push_back(edge<T>(from, to, cost, m));
(*this)[from].push_back(edge<T>(from, to, cost, m++));
}else{
if(from > to) swap(from, to);
es.push_back(edge<T>(from, to, cost, m));
(*this)[from].push_back(edge<T>(from, to, cost, m));
(*this)[to].push_back(edge<T>(to, from, cost, m++));
}
}
int get_vnum(){
return n;
}
int get_enum(){
return m;
}
bool get_dir(){
return dir;
}
edge<T> get_edge(int i){
return es[i];
}
edges<T> get_edge_set(){
return es;
}
};
template<typename T>
struct redge{
int from, to;
T cap, cost;
int rev;
redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};
template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;
template<typename T>
struct dinic{
int n;
residual_graph<T> graph;
dinic(residual_graph<T> &graph_){
n = (int)graph_.size();
graph.resize(n);
for(int from=0; from<n; from++){
for(redge<T> e : graph_[from]){
graph[from].push_back(redge<T>(e.to, e.cap, e.cost, (int)graph[e.to].size()));
graph[e.to].push_back(redge<T>(from, 0, e.cost, (int)graph[from].size()-1));
}
}
}
T max_flow(int s, int t){
residual_graph<T> rgraph(n);
vector<int> level(n);
vector<int> iter(n);
for(int from=0; from<n; from++) for(redge<T> e : graph[from]) rgraph[from].push_back(e);
function<void()> bfs = [&](){
for(int v=0; v<n; v++) level[v]=-1;
queue<int> Q;
level[s] = 0;
Q.push(s);
while(!Q.empty()){
int v = Q.front();
Q.pop();
for(redge<T> e : rgraph[v]){
if(e.cap > 0 && level[e.to] < 0){
level[e.to] = level[v] + 1;
Q.push(e.to);
}
}
}
};
function<T(int, T)> dfs = [&](int v, T f){
if(v == t) return f;
for(int &i=iter[v]; i<(int)rgraph[v].size(); i++){
redge<T> &e = rgraph[v][i];
if(e.cap > 0 && level[v] < level[e.to]){
T d = dfs(e.to, min(f, e.cap));
if(d > 0){
e.cap -= d;
rgraph[e.to][e.rev].cap += d;
return d;
}
}
}
return (T)0;
};
T flow = 0;
for(;;){
bfs();
if(level[t] < 0) return flow;
for(int v=0; v<n; v++) iter[v] = 0;
T f;
while((f = dfs(s, LINF)) > 0) flow += f;
}
}
};
void solve(){
ll ans = 0LL;
int N; cin >> N;
vector<ll> P(N);
for(int i=0; i<N; i++){
cin >> P[i];
if(0 < P[i]) ans += P[i];
}
int M; cin >> M;
vector<int> U(M), V(M);
for(int i=0; i<M; i++){
cin >> U[i] >> V[i];
U[i]--; V[i]--;
}
int K; cin >> K;
vector<int> A(K), B(K);
vector<ll> S(K);
for(int i=0; i<K; i++){
cin >> A[i] >> B[i] >> S[i];
A[i]--; B[i]--;
ans += S[i];
}
residual_graph<ll> G(N+K+2);
int s = N+K, t = N+K+1;
for(int i=0; i<N; i++){
if(0 < P[i]) G[i].pb(redge<ll>(t, P[i]));
else G[s].pb(redge<ll>(i, -P[i]));
}
for(int i=0; i<M; i++) G[U[i]].pb(redge<ll>(V[i], LINF));
for(int i=0; i<K; i++){
G[s].pb(redge<ll>(N+i, 0LL));
G[A[i]].pb(redge<ll>(N+i, LINF));
G[B[i]].pb(redge<ll>(N+i, LINF));
G[N+i].pb(redge<ll>(t, S[i]));
}
dinic<ll> dc(G);
ans -= dc.max_flow(s, t);
cout << ans << endl;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int T=1;
//cin >> T;
while(T--) solve();
}