제출 #13028

#제출 시각아이디문제언어결과실행 시간메모리
13028ainta통행료 (APIO13_toll)C++98
16 / 100
2 ms8324 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...