Submission #159297

#	Time	Username	Problem	Language	Result	Execution time	Memory
159297		Dat160601	Toll (APIO13_toll)	C++17	100 / 100	1824 ms	18736 KiB

toll

#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 = tree[i].se.fi, v = tree[i].se.se;
		if(unionset(u, v)){
			kruskal[u].pb(mp(v, tree[i].fi));
			kruskal[v].pb(mp(u, tree[i].fi));
		}
		else rem.pb(tree[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));
		}
		if(!ok) continue;
		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;
}

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