// created by Dinh Manh Hung
// tht.onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert
typedef int ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
char co;
for (co = getchar(); co < '0' || co > '9'; co = getchar());
int xo = co - '0';
for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
xo = xo * 10 + co - '0';
return xo;
}
void WriteInt(int xo)
{
if (xo > 9)
WriteInt(xo / 10);
putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/
// ================= Solution =================//
ll n,m,k;
const int N=1e5+5;
const int M=3e5+5;
bool check1[M];
bool check2[M];
struct pt{
ll a,b,c;
}edges[M],edgesa[25];
ll cnt[N];
long long dem[N];
int cost[N];
ll mau[N];
vector <ll> need,tmp;
vector <ii> vt[N];
struct DSU{
ll lab[N];
void makeset()
{
for (int i=1;i<=n;i++)
{
lab[i]=-1;
}
}
void makeseta(int u)
{
lab[u]=-1;
}
ll findset(int u)
{
if (lab[u]<0)
{
return u;
}
return lab[u]=findset(lab[u]);
}
void Union(int r,int s)
{
if (lab[r]>lab[s])
{
swap(r,s);
}
lab[r]+=lab[s];
lab[s]=r;
}
} dsu;
bool cmp(pt u,pt v)
{
return u.c<v.c;
}
ll sz[N];
ll cha[N];
long long dd[N];
void dfs(int u,int vv)
{
for (auto v:vt[u])
{
if (v.fi==vv)
{
continue;
}
cha[v.fi]=u;
sz[v.fi]=sz[u]+1;
dfs(v.fi,u);
}
}
void solve1(int u,int v,ll w)
{
if (sz[u]>sz[v])
{
swap(u,v);
}
while (sz[u]<sz[v])
{
cost[v]=min(cost[v],w);
v=cha[v];
}
while (u!=v)
{
cost[u]=min(cost[u],w);
cost[v]=min(cost[v],w);
u=cha[u];
v=cha[v];
}
}
long long ans;
void dfssolve(int u,int vv)
{
dd[u]=dem[u];
for (auto v:vt[u])
{
if (v.fi==vv)
{
continue;
}
dfssolve(v.fi,u);
if (v.se==1)
{
ans+=cost[v.fi]*dd[v.fi];
}
dd[u]+=dd[v.fi];
}
}
vector <ll> opt;
long long solve(int MASK)
{
ans=0;
opt.clear();
for (auto v:tmp)
{
dsu.makeseta(v);
vt[v].clear();
cost[v]=1e9+5;
}
for (int i=1;i<=k;i++)
{
if (readbit(MASK,i-1)==1)
{
ll aa=mau[edgesa[i].a];
ll bb=mau[edgesa[i].b];
ll a1=dsu.findset(aa);
ll a2=dsu.findset(bb);
if (a1==a2)
{
return -1;
}
vt[aa].pb({bb,1});
vt[bb].pb({aa,1});
dsu.Union(a1,a2);
}
}
for (auto v:need)
{
ll aa=mau[edges[v].a];
ll bb=mau[edges[v].b];
ll a1=dsu.findset(aa);
ll a2=dsu.findset(bb);
if (a1!=a2)
{
vt[aa].pb({bb,0});
vt[bb].pb({aa,0});
dsu.Union(a1,a2);
}
else opt.pb(v);
}
sz[mau[1]]=0;
dfs(mau[1],-1);
for (auto v:opt)
{
ll aa=mau[edges[v].a];
ll bb=mau[edges[v].b];
solve1(aa,bb,edges[v].c);
}
dfssolve(mau[1],-1);
return ans;
}
void optmushnpr()
{
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
{
cin>>edges[i].a>>edges[i].b>>edges[i].c;
}
for (int i=1;i<=k;i++)
{
cin>>edgesa[i].a>>edgesa[i].b;
}
for (int i=1;i<=n;i++)
{
cin>>cnt[i];
}
dsu.makeset();
sort (edges+1,edges+m+1,cmp);
for (int i=1;i<=m;i++)
{
ll aa=dsu.findset(edges[i].a);
ll bb=dsu.findset(edges[i].b);
if (aa!=bb)
{
check1[i]=true;
dsu.Union(aa,bb);
}
}
dsu.makeset();
for (int i=1;i<=k;i++)
{
ll aa=dsu.findset(edgesa[i].a);
ll bb=dsu.findset(edgesa[i].b);
if (aa!=bb)
{
dsu.Union(aa,bb);
}
}
for (int i=1;i<=m;i++)
{
ll aa=dsu.findset(edges[i].a);
ll bb=dsu.findset(edges[i].b);
if (aa!=bb)
{
check2[i]=true;
dsu.Union(aa,bb);
}
}
dsu.makeset();
for (int i=1;i<=m;i++)
{
if (check1[i]==true)
{
if (check2[i]==true)
{
dsu.Union(dsu.findset(edges[i].a),dsu.findset(edges[i].b));
}
else
{
need.pb(i);
}
}
}
for (int i=1;i<=n;i++)
{
ll aa=dsu.findset(i);
mau[i]=aa;
dem[aa]+=cnt[i];
if (aa==i)
{
tmp.pb(i);
}
}
long long res=0;
for (int i=mask(k-min(k,2));i<mask(k);i++)
{
res=max(res,solve(i));
}
cout<<res;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);}
int tests;
tests=1;
//cin>>tests;
while (tests--){optmushnpr();}
}
// goodbye see ya
Compilation message
toll.cpp: In function 'long long int solve(int)':
toll.cpp:177:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
177 | if (readbit(MASK,i-1)==1)
| ~^~
toll.cpp:24:27: note: in definition of macro 'readbit'
24 | #define readbit(x,i) ((x>>i)&1)
| ^
toll.cpp: In function 'int main()':
toll.cpp:303:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
303 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:304:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
304 | freopen(task".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
147 ms |
8140 KB |
Output is correct |
| 8 |
Correct |
155 ms |
8164 KB |
Output is correct |
| 9 |
Correct |
163 ms |
8196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
147 ms |
8140 KB |
Output is correct |
| 8 |
Correct |
155 ms |
8164 KB |
Output is correct |
| 9 |
Correct |
163 ms |
8196 KB |
Output is correct |
| 10 |
Correct |
1039 ms |
8480 KB |
Output is correct |
| 11 |
Correct |
1444 ms |
8436 KB |
Output is correct |
| 12 |
Correct |
1413 ms |
8364 KB |
Output is correct |
