| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13028 |
2015-01-26T08:27:00 Z |
ainta |
Toll (APIO13_toll) |
C++ |
|
2 ms |
8324 KB |
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000], L[101000];
int n, m, K, Uni[101000], cnt, Num[101000], TP[101000];
int EE[22][22], LL[22][22], CC[22];
bool CK[22][22];
long long P[22];
int find(int a){
return a == Uni[a] ? a : Uni[a] = find(Uni[a]);
}
struct Edge{
int a, b, c;
bool operator<(const Edge &p)const{
return c < p.c;
}
}inpp[101000], w[20], de[20];
void Add(int a, int b, int c){
E[a].push_back(b); E[b].push_back(a);
L[a].push_back(c); L[b].push_back(c);
}
int MMax, Ma, Mb;
bool DFS1(int a, int pp, int ed){
bool ck = false;
if (ed == a)ck = true;
for (int i = 0; i < E[a].size(); i++){
if (E[a][i] == pp || !E[a][i])continue;
if (DFS1(E[a][i], a, ed)){
if (MMax < L[a][i]){
MMax = L[a][i], Ma = a, Mb = E[a][i];
}
ck = true;
}
}
return ck;
}
void Del2(int a, int b){
int i;
for (i = 0; i < E[a].size(); i++){
if (E[a][i] == b)E[a][i] = 0;
}
}
void Del(int a, int b){
Del2(a, b); Del2(b, a);
}
void DFS2(int a){
Num[a] = cnt;
for (int i = 0; i < E[a].size(); i++){
if(E[a][i] && !Num[E[a][i]])DFS2(E[a][i]);
}
}
void Add2(int a, int b, int c, bool ck){
EE[a][CC[a]] = b; EE[b][CC[b]] = a;
LL[a][CC[a]] = LL[b][CC[b]] = c;
CK[a][CC[a]] = CK[b][CC[b]] = ck;
CC[a]++, CC[b]++;
}
long long Res;
bool Mck;
bool DFS3(int a, int pp, int ed){
bool r = false;
if (ed == a)r = true;
for (int i = 0; i < CC[a]; i++){
if (EE[a][i] == pp)continue;
if (DFS3(EE[a][i], a, ed)){
if (MMax < LL[a][i]){
MMax = LL[a][i], Ma = a, Mb = EE[a][i], Mck = CK[a][i];
}
r = true;
}
}
return r;
}
void Del3(int a, int b){
int i, x;
for (i = 0; i < CC[a]; i++)if (EE[a][i] == b)break;
x = i;
for (i = x; i < CC[a] - 1; i++){
EE[a][i] = EE[a][i + 1], LL[a][i] = LL[a][i + 1], CK[a][i] = CK[a][i + 1];
}
CC[a]--;
}
long long S = 0;
long long Calc(int a, int pp){
int i;
long long t, r = P[a];
for (i = 0; i < CC[a]; i++){
if (EE[a][i] != pp){
t = Calc(EE[a][i], a);
if (CK[a][i])S += t*LL[a][i];
r += t;
}
}
return r;
}
void Do(int m){
if (m == K){
S = 0;
Calc(Num[1], 0);
Res = max(Res, S);
return;
}
Do(m + 1);
MMax = 0;
DFS3(w[m].a, 0, w[m].b);
int ta = Ma, tb = Mb, tc = MMax;
bool tck = Mck;
Del3(ta, tb); Del3(tb, ta);
Add2(w[m].a, w[m].b, tc, 1);
Do(m + 1);
Del3(w[m].a, w[m].b); Del3(w[m].b, w[m].a);
Add2(ta, tb, tc, tck);
}
int main()
{
int i, x, y, j, k;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < m; i++){
scanf("%d%d%d", &inpp[i].a, &inpp[i].b, &inpp[i].c);
}
sort(inpp, inpp + m);
for (i = 1; i <= n; i++)Uni[i] = i;
for (i = 0; i < m; i++){
x = find(inpp[i].a), y = find(inpp[i].b);
if (x != y){
Add(inpp[i].a, inpp[i].b, inpp[i].c);
Uni[x] = y;
}
}
for (i = 0; i < K; i++){
scanf("%d%d", &w[i].a, &w[i].b);
MMax = 0;
DFS1(w[i].a, 0, w[i].b);
for (j = 0; j < K; j++){
if (w[j].a == Ma && w[j].b == Mb)break;
if (w[j].a == Mb && w[j].b == Ma)break;
}
if (j == K){
de[cnt].a = Ma, de[cnt].b = Mb, de[cnt].c = MMax; cnt++;
}
Del(Ma, Mb);
Add(w[i].a, w[i].b, MMax);
}
for (k = 0; k < K; k++){
Del(w[k].a, w[k].b);
}
for (i = 1; i <= n; i++){
scanf("%d", &TP[i]);
}
cnt = 0;
for (i = 1; i <= n; i++){
if (!Num[i]){
cnt++;
DFS2(i);
}
}
for (i = 1; i <= n; i++)P[Num[i]] += TP[i];
for (i = 0; i < cnt - 1; i++){
Add2(Num[de[i].a], Num[de[i].b], de[i].c, 0);
}
for (i = 0; i < K; i++)w[i].a = Num[w[i].a], w[i].b = Num[w[i].b];
Do(0);
printf("%lld\n", Res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8324 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
