제출 #13028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13028		ainta	통행료 (APIO13_toll)	C++98	16 / 100	2 ms	8324 KiB

toll

#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);
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22