#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct Edg{
int s, e, c, i;
bool operator<(const Edg &oth) const {
return c < oth.c;
}
};
int n, m, k, s[21], e[21], p[100010], wh[100010], ch[300022], chk[300022], mi;
ll sp[22], a[22], cans;
vector<Edg> av, v, sv, t[100010], st[22];
struct Dsu{
int p[100010];
void ini(){
for(int i = 1; i <= n; i++) p[i] = i;
}
int fnd(int x){ return p[x] = (x == p[x] ? x : fnd(p[x])); }
void uni(int x, int y){ p[fnd(x)] = fnd(y); }
} D;
void bld(){
sort(v.begin(), v.end());
D.ini();
for(auto &i : v){
if(D.fnd(i.s) == D.fnd(i.e)) continue;
D.uni(i.s, i.e);
t[i.s].push_back(i);
t[i.e].push_back({i.e, i.s, i.c, i.i});
ch[i.i] = 1;
}
for(int i = 1; i <= k; i++) v.push_back({s[i], e[i], 0, m + i});
sort(v.begin(), v.end());
D.ini();
for(auto &i : v){
if(D.fnd(i.s) == D.fnd(i.e)) continue;
D.uni(i.s, i.e);
if(ch[i.i]) ch[i.i] = 0;
}
for(int i = 1; i <= m; i++) if(ch[i]) sv.push_back(av[i - 1]);
}
void sdfs(int x, int pv, int id){
wh[x] = id;
sp[id] += (ll)p[x];
for(auto &i : t[x]){
if(i.e == pv) continue;
if(ch[i.i]) continue;
sdfs(i.e, x, id);
}
}
ll adfs(int x, int p){
a[x] = sp[x];
for(auto &i : st[x]){
if(chk[i.i]) continue;
if(i.e == p) continue;
ll t = adfs(i.e, x);
a[x] += t;
if(i.i > m) cans += (ll)i.c * t;
}
return a[x];
}
int gdfs(int x, int p, int e, int t, queue<int> &q){
for(auto &i : st[x]){
if(chk[i.i]) continue;
if(i.e == p) continue;
if(gdfs(i.e, x, e, t, q)){
if(t == 0 && i.i <= m){
if(!mi || av[mi - 1].c < i.c) mi = i.i;
}
else if(t == 1 && i.i > m){
q.push(i.c);
i.c = min(i.c, av[mi - 1].c);
}
else if(t == 2 && i.i > m){
i.c = q.front();
q.pop();
}
return 1;
}
}
return (x == e);
}
ll btk(int x){
if(x > k){ cans = 0; adfs(wh[1], 0); return cans; }
ll ret = btk(x + 1);
mi = 0;
queue<int> q;
gdfs(s[x], 0, e[x], 0, q);
if(!mi) return ret;
gdfs(s[x], 0, e[x], 1, q);
st[s[x]].push_back({s[x], e[x], av[mi - 1].c, m + x});
st[e[x]].push_back({e[x], s[x], av[mi - 1].c, m + x});
chk[mi] = 1;
ret = max(ret, btk(x + 1));
chk[mi] = 0;
st[s[x]].pop_back();
st[e[x]].pop_back();
gdfs(s[x], 0, e[x], 2, q);
return ret;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1, x, y, c; i <= m; i++){
scanf("%d%d%d", &x, &y, &c);
v.push_back({x, y, c, i});
}
av = v;
for(int i = 1; i <= k; i++){
scanf("%d%d", s + i, e + i);
}
for(int i = 1; i <= n; i++) scanf("%d", p + i);
bld();
for(int i = 1, cnt = 1; i <= n; i++){
if(!wh[i]){
sdfs(i, 0, cnt++);
}
}
for(int i = 1; i <= k; i++){ s[i] = wh[s[i]]; e[i] = wh[e[i]]; }
for(auto &i : sv){
int x = wh[i.s];
int y = wh[i.e];
st[x].push_back({x, y, i.c, i.i});
st[y].push_back({y, x, i.c, i.i});
}
printf("%lld\n", btk(1));
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:111:29: 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:113:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &c);
^
toll.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", s + i, e + i);
^
toll.cpp:120:48: 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", p + i);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
7888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
7888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
7888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7888 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
7888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
