#include <bits/stdc++.h>
using namespace std;
struct edge{
int x, y, k, i;
bool operator < (const edge &aux)const{
if(k != aux.k) return k < aux.k;
}
};
struct dsu{
int tt[100005], RG[100005];
void ini(int n){
for(int i = 1; i <= n ; ++i)
tt[i] = i, RG[i] = 1;
}
inline int Find(int x){
int R = x;
while(R != tt[R]) R = tt[R];
while(x != tt[x]){
int aux = tt[x];
tt[x] = R; x = aux;
}
return R;
}
inline void Union(int x, int y){
if(RG[x] > RG[y]) tt[y] = x;
else if(RG[x] < RG[y]) tt[x] = y;
else{
++RG[x];
tt[y] = x;
}
}
};
dsu D;
edge a[310005], b[25];
vector <edge> sv;
vector <edge> v[100005];
vector <edge> v2[25];
bool val[25];
int TT[25], h[25], pr[25];
long long sum[25], p[25];
int nrp[100005], tag[100005];
bool ch[310000];
int n, m, k, NR;
inline void precomp(){
D.ini(n);
sort(a + 1, a + m + 1);
for(int i = 1; i <= m ; ++i){
if(D.Find(a[i].x) != D.Find(a[i].y)){
D.Union(D.Find(a[i].x), D.Find(a[i].y));
ch[a[i].i] = 1;
}
}
for(int i = 1; i <= k ; ++i){
b[i].i = m + i;
b[i].k = 0;
a[++m] = b[i];
}
sort(a + 1, a + m + 1);
D.ini(n);
for(int i = 1; i <= m ; ++i){
if(D.Find(a[i].x) != D.Find(a[i].y)){
D.Union(D.Find(a[i].x), D.Find(a[i].y));
if(ch[a[i].i]){
v[a[i].x].push_back(a[i]);
v[a[i].y].push_back({a[i].y, a[i].x, a[i].k, a[i].i});
}
ch[a[i].i] = 0;
}
}
for(int i = 1; i <= m ; ++i)
if(ch[a[i].i]) sv.push_back(a[i]);
}
void dfs(int nod){
p[tag[nod]] += nrp[nod];
for(auto it : v[nod]){
if(tag[it.y]) continue ;
tag[it.y] = tag[nod];
dfs(it.y);
}
}
void dfs2(int nod){
sum[nod] = p[nod];
for(auto it : v2[nod]){
if(TT[it.x] == it.y) continue ;
TT[it.y] = it.x;
h[it.y] = h[it.x] + 1;
dfs2(it.y);
sum[it.x] += sum[it.y];
if(it.i == 1) val[it.y] = 1;
}
}
inline long long solve(int mask){
for(int i = 1; i <= NR ; ++i) v2[i].clear();
memset(val, 0, sizeof(val));
memset(sum, 0, sizeof(sum));
memset(pr, 0x3f, sizeof(pr));
if(mask == 1048575){
bool ok = 0;
}
D.ini(NR);
for(int i = 1; i <= k ; ++i){
if(((1 << (i - 1)) & mask)){
if(D.Find(b[i].x) == D.Find(b[i].y)) return -1;
D.Union(D.Find(b[i].x), D.Find(b[i].y));
v2[b[i].x].push_back({b[i].x, b[i].y, 0, 1});
v2[b[i].y].push_back({b[i].y, b[i].x, 0, 1});
}
}
vector <edge> nv;
for(auto it : sv){
if(D.Find(it.x) != D.Find(it.y)){
D.Union(D.Find(it.x), D.Find(it.y));
v2[it.x].push_back({it.x, it.y, 0, 0});
v2[it.y].push_back({it.y, it.x, 0, 0});
}
else nv.push_back(it);
}
dfs2(1);
for(auto it : nv){
int x = it.x, y = it.y, k = it.k;
if(h[x] < h[y]) swap(x, y);
while(h[x] != h[y]){
pr[x] = min(pr[x], k);
x = TT[x];
}
while(x != y){
pr[x] = min(pr[x], k);
pr[y] = min(pr[y], k);
x = TT[x]; y = TT[y];
}
}
long long ans = 0;
for(int i = 2; i <= NR ; ++i)
if(val[i]) ans += 1LL * sum[i] * pr[i];
return ans;
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m ; ++i)
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k), a[i].i = i;
for(int i = 1; i <= k ; ++i)
scanf("%d%d", &b[i].x, &b[i].y);
precomp();
for(int i = 1; i <= n ; ++i) scanf("%d", &nrp[i]);
for(int i = 1; i <= n ; ++i){
if(tag[i]) continue ;
tag[i] = ++NR;
dfs(i);
}
for(auto &it : sv) it.x = tag[it.x], it.y = tag[it.y];
sort(sv.begin(), sv.end());
for(int i = 1; i <= k ; ++i) b[i].x = tag[b[i].x], b[i].y = tag[b[i].y];
long long Sol = 0;
for(int i = 1; i < (1 << k) ; ++i) Sol = max(Sol, solve(i));
printf("%lld", Sol);
return 0;
}
Compilation message
toll.cpp: In function 'long long int solve(int)':
toll.cpp:116:14: warning: unused variable 'ok' [-Wunused-variable]
bool ok = 0;
^~
toll.cpp: In function 'int main()':
toll.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:167:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k), a[i].i = i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
toll.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &b[i].x, &b[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:174:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n ; ++i) scanf("%d", &nrp[i]);
~~~~~^~~~~~~~~~~~~~~
toll.cpp: In member function 'bool edge::operator<(const edge&) const':
toll.cpp:10:5: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3072 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2944 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3072 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 7 |
Incorrect |
207 ms |
15324 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3072 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 7 |
Incorrect |
207 ms |
15324 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
