#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
#ifndef LOCAL
static char buf[buf_size];
static int len = 0, pos = 0;
if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
if(pos == len) return -1;
return buf[pos++];
#endif
}
inline int readChar(){
#ifndef LOCAL
int c = getChar();
while(c <= 32) c = getChar();
return c;
#else
char c; cin >> c; return c;
#endif
}
template <class T>
inline T readInt(){
#ifndef LOCAL
int s = 1, c = readChar();
T x = 0;
if(c == '-') s = -1, c = getChar();
while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
#else
T x; cin >> x; return x;
#endif
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
if(x < 0) writeChar('-'), x = -x;
char s[24]; int n = 0;
while(x || !n) s[n++] = '0' + x % 10, x /= 10;
while(n--) writeChar(s[n]);
if(end) writeChar(end);
}
inline void writeWord(const char *s){
while(*s) writeChar(*s++);
}
struct Flusher{
~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;
struct edge
{
ll u, v, cost;
bool operator < (const edge &xx) const
{
return cost < xx.cost;
}
};
ll n, m, K;
ll all, bll, cll;
vector<edge> edg;
vector< pair<pll, ll> > mst[3];
set< pair<pll, ll> > st;
pll ne[100010];
ll a[100010];
ll p[100010], ra[100010];
vector<ll> V;
vector< pair<pll, ll> > vec[30];
ll sum[100010];
ll siz;
ll grp[100010];
ll chk[30], last[30];
ll dp[30];
ll ans;
ll dep[30];
ll ffind(ll here)
{
if(here == p[here])
return here;
return p[here] = ffind(p[here]);
}
void uunion(ll X, ll Y)
{
X = ffind(X);
Y = ffind(Y);
if(X == Y)
return;
if(ra[X] < ra[Y])
p[X] = Y;
else if(ra[X] > ra[Y])
p[Y] = X;
else
{
p[X] = Y;
ra[Y]++;
}
}
void MST(ll num)
{
for(ll i = 1 ; i <= n ; i++)
p[i] = i, ra[i] = 0;
sort(edg.begin(), edg.end());
for(auto &i : edg)
{
if(ffind(i.u) == ffind(i.v))
continue;
uunion(i.u, i.v);
mst[num].push_back({{min(i.u, i.v), max(i.u, i.v)}, i.cost});
}
}
void dfs(ll here, ll pa)
{
last[here] = pa;
for(auto &i : vec[here])
{
if(i.fi.fi == pa)
continue;
dfs(i.fi.fi, here);
}
}
void add_edge(ll I)
{
ll uu = ne[I].fi;
ll vv = ne[I].se;
dfs(uu, 0);
for(ll i = 1 ; i <= siz ; i++)
chk[i] = 0;
for(ll i = vv ; i != 0 ; i = last[i])
chk[i] = 1;
ll bi = -INF;
for(ll i = 1 ; i <= siz ; i++)
{
for(auto &j : vec[i])
{
if(chk[i] && chk[j.fi.fi] && j.se == 0)
bi = max(bi, j.fi.se);
}
}
if(bi == -INF)
return;
vector< pair<pll, ll> > help[30];
for(ll i = 1 ; i <= siz ; i++)
{
for(auto &j : vec[i])
{
if(j.se == 1 && j.fi.se > bi && chk[i] && chk[j.fi.fi])
help[i].push_back({{j.fi.fi, bi}, j.se});
else if(j.se == 0 && j.fi.se == bi)
continue;
else
help[i].push_back(j);
}
}
help[uu].push_back({{vv, bi}, 1});
help[vv].push_back({{uu, bi}, 1});
for(ll i = 1 ; i <= siz ; i++)
vec[i] = help[i];
}
void dfs2(ll here, ll pa)
{
dp[here] = sum[here];
dep[here] = dep[pa] + 1;
for(auto &i : vec[here])
{
if(i.fi.fi == pa)
continue;
dfs2(i.fi.fi, here);
dp[here] += dp[i.fi.fi];
}
}
ll hehe = 0;
void f(ll here)
{
if(here > K)
{
ll gap = 0;
dfs2(grp[1], 0);
for(ll i = 1 ; i <= siz ; i++)
{
for(auto &j : vec[i])
{
if(j.se == 0)
continue;
if(dep[j.fi.fi] < dep[i])
continue;
gap += dp[j.fi.fi] * j.fi.se;
}
}
ans = max(ans, gap);
return;
}
f(here + 1);
vector< pair<pll, ll> > tmp[30];
for(ll i = 1 ; i <= siz ; i++)
tmp[i] = vec[i];
add_edge(here);
f(here + 1);
for(ll i = 1 ; i <= siz ; i++)
vec[i] = tmp[i];
}
int main(void)
{
fastio
//cin >> n >> m >> K;
n = readInt();
m = readInt();
K = readInt();
for(ll i = 1 ; i <= m ; i++)
{
//cin >> all >> bll >> cll;
all = readInt();
bll = readInt();
cll = readInt();
edg.push_back({all, bll, cll});
}
for(ll i = 1 ; i <= K ; i++)
{
ne[i].fi = readInt();
ne[i].se = readInt();
//cin >> ne[i].fi >> ne[i].se;
}
for(ll i = 1 ; i <= n ; i++)
{
a[i] = readInt();
//cin >> a[i];
}
MST(0);
for(ll i = 1 ; i <= K ; i++)
edg.push_back({ne[i].fi, ne[i].se, 0});
MST(1);
for(auto &i : mst[1])
st.insert(i);
for(ll i = 1 ; i <= n ; i++)
p[i] = i, ra[i] = 0;
for(auto &i : mst[0])
{
if(st.find(i) == st.end())
mst[2].push_back(i);
else
uunion(i.fi.fi, i.fi.se);
}
for(ll i = 1 ; i <= n ; i++)
V.push_back(ffind(i));
compress(V);
siz = (ll)V.size();
for(ll i = 1 ; i <= n ; i++)
{
ll w = ffind(i);
w = lower_bound(V.begin(), V.end(), w) - V.begin() + 1;
grp[i] = w;
sum[w] += a[i];
}
for(auto &i : mst[2])
{
ll v1 = ffind(i.fi.fi);
ll v2 = ffind(i.fi.se);
v1 = lower_bound(V.begin(), V.end(), v1) - V.begin() + 1;
v2 = lower_bound(V.begin(), V.end(), v2) - V.begin() + 1;
vec[v1].push_back({{v2, i.se}, 0});
vec[v2].push_back({{v1, i.se}, 0});
}
for(ll i = 1 ; i <= K ; i++)
{
ne[i].fi = lower_bound(V.begin(), V.end(), ffind(ne[i].fi)) - V.begin() + 1;
ne[i].se = lower_bound(V.begin(), V.end(), ffind(ne[i].se)) - V.begin() + 1;
}
f(1);
writeInt(ans);
flusher();
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:358:10: error: no match for call to '(Flusher) ()'
358 | flusher();
| ^
