| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122445 |
2019-06-28T08:38:43 Z |
임유진(#2991) |
Toll (APIO13_toll) |
C++14 |
|
5 ms |
768 KB |
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
#define MAXN 1005
#define MAXM 5005
#define MAXK 15
const int INF=1e6+5;
int A[MAXM], B[MAXM], C[MAXM];
int p[MAXN];
int uni[MAXN];
vector<pii> e[MAXN];
int dp[MAXN], dep[MAXN];
pii par[MAXN];
bool cmp(int a, int b){
return C[a]<C[b];
}
int guni(int x){
if(x==uni[x]) return x;
return uni[x]=guni(uni[x]);
}
void dfs(int x){
//printf("dfs(%d), par[%d]=(%d, %d)\n", x, x, par[x].first, par[x].second);
dp[x] = p[x];
for(auto a : e[x]) if( dp[a.first] == 0){
par[a.first]=make_pair(x, a.second);
dep[a.first] = dep[x] + 1;
dfs(a.first);
dp[x] += dp[a.first];
}
//printf("dp[%d]=%d\n", x, dp[x]);
}
int main(){
int N, M, K;
int x[MAXK], y[MAXK];
int es[MAXM];
int v[MAXK];
bitset<MAXN> chk;
lint ans=0;
scanf("%d%d%d", &N, &M, &K);
for(int i=0; i<M; i++) scanf("%d%d%d", A+i, B+i, C+i);
for(int i=0; i<K; i++) scanf("%d%d", x+i, y+i);
for(int i=1; i<=N; i++) scanf("%d", p+i);
for(int i=0; i<M; i++) es[i]=i;
sort(es, es+M, cmp);
for(int i=1; i<(1<<K); i++){
bool ava=true;
for(int j=1; j<=N; j++) {
uni[j]=j;
e[j].clear();
}
for(int j=0; j<K; j++) if((1<<j)&i) {
if(guni(x[j])==guni(y[j])){
ava=false;
break;
}
uni[guni(x[j])] = guni(y[j]);
e[x[j]].push_back( make_pair(y[j], j) );
e[y[j]].push_back( make_pair(x[j], j) );
v[j] = INF;
}
if(!ava) continue;
//printf("i=%d\n", i);
for(int j=0; j<M; j++) chk[j]=false;
for(int j=0; j<M; j++) if(guni(A[es[j]]) != guni(B[es[j]])) {
uni[guni(A[es[j]])] = guni(B[es[j]]);
e[A[es[j]]].push_back(make_pair(B[es[j]], -1));
e[B[es[j]]].push_back(make_pair(A[es[j]], -1));
chk[j] = true;
}
for(int j=1; j<=N; j++) dp[j] = 0;
dep[1] = 0;
dfs(1);
for(int j=0; j<M; j++) if(!chk[j]) {
int r = A[es[j]], s = B[es[j]];
//printf("r=%d, s=%d\n", r, s);
while(dep[r] > dep[s]){
if(par[r].second != -1) v[ par[r].second ] = min( v[ par[r].second ], C[es[j]] );
r = par[r].first;
}
while(dep[s] > dep[r]){
if( par[s].second != -1) v[ par[s].second ] = min( v[ par[s].second ], C[es[j]] );
s = par[s].first;
}
while( r != s ) {
if( par[s].second != -1) v[ par[s].second ] = min( v[ par[s].second ], C[es[j]] );
s = par[s].first;
if( par[r].second != -1) v[ par[r].second ] = min( v[ par[r].second ], C[es[j]] );
r = par[r].first;
}
}
//for(int j=0; j<K; j++) if((1<<j)&i) printf("v[%d]=%d\n", j, v[j]);
lint sum = 0;
for(int j=0; j<K; j++) if((1<<j) & i) sum += (lint)v[j] * min(dp[x[j]], dp[y[j]]);
ans=max(ans, sum);
}
printf("%lld", ans);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:53:7: 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:54:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<M; i++) scanf("%d%d%d", A+i, B+i, C+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:55:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<K; i++) scanf("%d%d", x+i, y+i);
~~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:56:31: 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);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
