結果
| 問題 |
No.2604 Initial Motion
|
| コンテスト | |
| ユーザー |
 asaringo
|
| 提出日時 | 2024-01-13 01:07:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 918 ms / 3,000 ms |
| コード長 | 9,238 bytes |
| コンパイル時間 | 2,944 ms |
| コンパイル使用メモリ | 219,528 KB |
| 最終ジャッジ日時 | 2025-02-18 19:30:18 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}
struct MinCostFlow{
private:
static const ll inf = LLONG_MAX;
struct edge
{
int to , rev;
ll cost , cap;
};
struct edge_ {
int from, to;
ll cap, flow , cost;
};
int n;
vector<vector<edge>> G;
vector<pair<int,int>> pos;
vector<ll> dist , h;
vector<int> prevv , preve;
void init_(int n_){
G.resize(n_);
dist.resize(n_);
h.resize(n_);
prevv.resize(n_);
preve.resize(n_);
}
void add_edge_(int from, int to, ll cap, ll cost){
pos.push_back({from, G[from].size()});
int from_id = int(G[from].size());
int to_id = int(G[to].size());
if (from == to) to_id++;
G[from].push_back(edge{to, to_id, cost, cap});
G[to].push_back(edge{from, from_id, -cost, 0});
}
int edge_size_(){
return (int)pos.size();
}
edge_ get_edge_(int k){
edge e = G[pos[k].first][pos[k].second];
edge re = G[e.to][e.rev];
return edge_{pos[k].first, e.to, e.cap + re.cap, re.cap, e.cost};
}
vector<edge_> get_edges_(){
int m = (int)pos.size();
vector<edge_> res;
for(int i = 0; i < m; i++) res.push_back(get_edge_(i));
return res;
}
vector<pair<ll,ll>> min_flow_(int s, int t, ll flow_limit){
vector<pair<ll,ll>> res = {{0,0}};
ll flow = 0;
ll cost = 0;
ll prev_cost_per_flow = -1;
fill(h.begin(), h.end(),0);
while(flow < flow_limit){
fill(dist.begin(),dist.end(),9223372036854775807LL);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> que;
dist[s] = 0;
que.push(pair<ll,int>(0,s));
while(!que.empty()){
pair<ll,int> p = que.top(); que.pop();
int v = p.second;
if(dist[v] < p.first) continue;
for(int i = 0; i < G[v].size(); i++){
edge e = G[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + h[v] - h[e.to] + e.cost){
dist[e.to] = dist[v] + h[v] - h[e.to] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
que.push(pair<ll,int>(dist[e.to],e.to));
}
}
}
if(dist[t] == inf) break; // 総流量fを流すことができなかった
for(int i = 0; i < n; i++) h[i] += dist[i];
ll d = flow_limit - flow;
for(int v = t; v != s; v = prevv[v]) d = min(d,G[prevv[v]][preve[v]].cap);
for(int v = t; v != s; v = prevv[v]){
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[e.to][e.rev].cap += d;
}
cost += h[t] * d;
flow += d;
if(prev_cost_per_flow == h[t]) res.pop_back();
res.push_back({flow, cost});
prev_cost_per_flow = h[t];
}
return res;
}
public:
MinCostFlow() {}
MinCostFlow(int n_): n(n_) { init_(n); }
void init(int n) { init_(n); }
int edge_size() { return edge_size_(); }
void add_edge(int from , int to , ll cap, ll cost) { add_edge_(from, to, cap, cost); }
edge_ get_edge(int k) { return get_edge_(k); }
vector<edge_> get_edges() { return get_edges_(); }
ll min_cost(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit).back().second; }
pair<ll,ll> min_cost_flow(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit).back(); }
vector<pair<ll,ll>> slope(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit); }
};
// function : return : description
// --------------------------------------------------------------------------------------------------------------------------------------------
// constructor() : :
// constructor(n) : : サイズ n で初期化する
// init(int n) : void : サイズ n で初期化する
// add_edge(int from, int to, ll cap, ll cost) : void : 容量が cap の from から to への辺を張る
// edge_size() : int : 辺のサイズを返す
// get_edge(int k) : void : k 番目の辺の情報(始点, 行き先, 容量, コスト, 流量)を返す
// get_edges() : vector<edge_> : 全ての辺の情報(始点, 行き先, 容量, コスト, 流量)を返す
// min_cost(int s, int t) : ll : s から t へ目一杯流した時の最小コストを返す
// mix_cost(int s, int t, flow_limit) : ll : s から t へ flow_limit まで目一杯流した時の最小コストを返す
// mix_cost_flow(int s, int t) : pair<ll,ll> : s から t へまで目一杯流した時の 流量, 最小コストを返す
// mix_cost_flow(int s, int t, flow_limit) : pair<ll,ll> : s から t へ flow_limit まで目一杯流した時の流量, 最小コストを返す
// slope(int s, int t) : vector<pair<ll,ll>> : s から t へまで目一杯流した時の流量, コストの折線グラフを返す
// slope(int s, int t, flow_limit) : vector<pair<ll,ll>> : s から t へ flow_limit まで目一杯流した時の流量, コストの折線グラフを返す
// --------------------------------------------------------------------------------------------------------------------------------------------
int n, m, k;
void solve(){
cin >> k >> n >> m;
vector<int> A(k), B(n);
cin >> A >> B;
MinCostFlow mcf(n+2);
ll inf = 1e12;
rep(i,m){
ll u, v, d;
cin >> u >> v >> d;
u--; v--;
mcf.add_edge(u,v,inf,d);
mcf.add_edge(v,u,inf,d);
}
rep(i,k) mcf.add_edge(n,A[i]-1,1,0);
rep(i,n) mcf.add_edge(i,n+1,B[i],0);
ll f = mcf.min_cost(n,n+1);
pt(f)
}
int main(){
fast_io
int t = 1;
// cin >> t;
rep(i,t) solve();
}