#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int N = 100001, K = 21, INF = 1e7;
vector<pair<int, int>> cg[K];
int p[N], r[N], np[N], par[K], uw[K], cnt[N];
ll val[K], sum[K];
int getp(int v) {
if (p[v] != v)
p[v] = getp(p[v]);
return p[v];
}
int merge(int u, int v) {
u = getp(u);
v = getp(v);
if (u == v)
return 0;
if (r[u] > r[v])
p[v] = u;
else {
p[u] = v;
if (r[u] == r[v])
r[v]++;
}
return 1;
}
void dfs(int v, int p) {
par[v] = p;
sum[v] = val[v];
for (auto &pp : cg[v]) {
if (pp.first == p)
continue;
uw[pp.first] = (pp.second == -1 ? INF : 0);
dfs(pp.first, v);
sum[v] += sum[pp.first];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> e(m, vector<int>(3)), ne(k, vector<int>(3, -1)), ce, de;
rep(i, m) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
e[i][1]--; e[i][2]--;
}
sort(all(e));
rep(i, n)
p[i] = i;
rep(i, k) {
cin >> ne[i][1] >> ne[i][2];
ne[i][1]--;
ne[i][2]--;
}
for (auto &pp : e)
if (merge(pp[1], pp[2]))
ne.push_back(pp);
rep(i, n) {
p[i] = i;
r[i] = 0;
}
for (auto &pp : ne) {
if (merge(pp[1], pp[2]) && pp[0] > -1)
ce.push_back(pp);
else if (pp[0] > -1)
de.push_back(pp);
}
rep(i, n) {
p[i] = i;
r[i] = 0;
}
for (auto &pp : ce)
merge(pp[1], pp[2]);
vector<int> li;
rep(i, n)
li.push_back(getp(i));
sort(all(li));
li.resize(unique(all(li)) - li.begin());
rep(i, n) {
np[i] = lower_bound(all(li), p[i]) - li.begin();
cout << np[i] << '\n';
cin >> cnt[i];
val[np[i]] += cnt[i];
}
rep(i, ne.size()) {
ne[i][1] = np[ne[i][1]];
ne[i][2] = np[ne[i][2]];
}
rep(i, de.size()) {
de[i][1] = np[de[i][1]];
de[i][2] = np[de[i][2]];
}
int nn = li.size(), rt = np[p[0]];
ll ans = 0, ca;
rep(i, 1 << k) {
int f = 0;
rep(j, nn) {
p[j] = j;
r[j] = 0;
cg[j].clear();
}
rep(j, k)
if ((i & (1 << j))) {
if (!merge(ne[j][1], ne[j][2])) {
f = 1;
break;
}
cg[ne[j][1]].push_back({ne[j][2], -1});
cg[ne[j][2]].push_back({ne[j][1], -1});
}
if (f)
continue;
vector<vector<int>> re;
for (auto &pp : de) {
if (merge(pp[1], pp[2])) {
cg[pp[1]].push_back({pp[2], pp[0]});
cg[pp[2]].push_back({pp[1], pp[0]});
}
else
re.push_back(pp);
}
dfs(rt, -1);
for (auto &pp : re) {
int v1 = pp[1], v2 = pp[2];
if (sum[v1] < sum[v2])
swap(v1, v2);
while (v2 != v1) {
uw[v2] = min(uw[v2], pp[0]);
v2 = par[v2];
}
}
ca = 0;
rep(i, nn)
ca += uw[i] * sum[i];
ans = max(ans, ca);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); i++)
^
toll.cpp:113:5: note: in expansion of macro 'rep'
rep(i, ne.size()) {
^~~
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); i++)
^
toll.cpp:117:5: note: in expansion of macro 'rep'
rep(i, de.size()) {
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
