| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159294 |
2019-10-22T06:42:39 Z |
Dat160601 |
Toll (APIO13_toll) |
C++17 |
|
4 ms |
2812 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair < int, pair <int, int> > Edge;
const int N = 1e5 + 7;
int n, m, k, u, v, w, a[N], pset[N], cnt = 0, num[N], dep[100];
long long ans = 0, f[100], dp[100], g[100];
pair <int, int> road[100], pr[100];
vector <Edge> ed, tree, rem, tmp;
vector < pair <int, int> > kruskal[N], edge[100];
int fset(int x){
if(pset[x] == x) return x;
return pset[x] = fset(pset[x]);
}
bool unionset(int x, int y){
x = fset(x), y = fset(y);
if(x == y) return false;
pset[x] = y;
return true;
}
void dfs(int u, int par){
num[u] = cnt;
f[cnt] += a[u];
for(int i = 0; i < (int)kruskal[u].size(); i++){
int v = kruskal[u][i].fi;
if(v == par) continue;
dfs(v, u);
}
}
void redfs(int u, int par){
g[u] = f[u];
for(int i = 0; i < (int)edge[u].size(); i++){
int v = edge[u][i].fi;
if(v == par) continue;
pr[v] = mp(u, edge[u][i].se);
dep[v] = dep[u] + 1;
redfs(v, u);
g[u] += g[v];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++){
cin >> u >> v >> w;
ed.pb(mp(w, mp(u, v)));
}
for(int i = 1; i <= n; i++) pset[i] = i;
sort(ed.begin(), ed.end());
for(int i = 0; i < m; i++){
int u = ed[i].se.fi, v = ed[i].se.se;
if(unionset(u, v)){
tree.pb(ed[i]);
}
}
for(int i = 1; i <= n; i++) pset[i] = i;
for(int i = 1; i <= k; i++){
cin >> road[i].fi >> road[i].se;
unionset(road[i].fi, road[i].se);
}
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i < (int)tree.size(); i++){
int u = ed[i].se.fi, v = ed[i].se.se;
if(unionset(u, v)){
kruskal[u].pb(mp(v, ed[i].fi));
kruskal[v].pb(mp(u, ed[i].fi));
}
else rem.pb(ed[i]);
}
for(int i = 1; i <= n; i++){
if(!num[i]){
++cnt;
dfs(i, i);
}
}
for(int mask = 0; mask < (1 << k); mask++){
for(int i = 1; i <= cnt; i++) pset[i] = i, dep[i] = 0, edge[i].clear();
bool ok = true;
long long res = 0;
for(int i = 0; i < k; i++){
dp[i + 1] = 1e9;
if(!(mask & (1 << i))) continue;
int u = road[i + 1].fi, v = road[i + 1].se;
u = num[u], v = num[v];
if(!unionset(u, v)){
ok = false;
break;
}
edge[u].pb(mp(v, i + 1));
edge[v].pb(mp(u, i + 1));
}
tmp.clear();
for(Edge x : rem){
int u = num[x.se.fi], v = num[x.se.se];
if(!unionset(u, v)){
tmp.pb(x);
}
else edge[u].pb(mp(v, 0)), edge[v].pb(mp(u, 0));
}
redfs(num[1], num[1]);
for(Edge x : tmp){
int u = num[x.se.fi], v = num[x.se.se];
if(dep[u] > dep[v]) swap(u, v);
while(dep[u] < dep[v]){
if(pr[v].se != 0) dp[pr[v].se] = min(dp[pr[v].se], 1LL * x.fi);
v = pr[v].fi;
}
while(u != v){
if(pr[v].se != 0) dp[pr[v].se] = min(dp[pr[v].se], 1LL * x.fi);
if(pr[u].se != 0) dp[pr[u].se] = min(dp[pr[u].se], 1LL * x.fi);
v = pr[v].fi;
u = pr[u].fi;
}
}
for(int i = 0; i < k; i++){
if(!(mask & (1 << i))) continue;
int u = road[i + 1].fi, v = road[i + 1].se;
u = num[u], v = num[v];
if(dep[u] > dep[v]) swap(u, v);
res += 1LL * dp[i + 1] * g[v];
}
ans = max(ans, res);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:89:8: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
bool ok = true;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
