oj.uz

답안 #159297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159297 2019-10-22T06:46:49 Z Dat160601 통행료 (APIO13_toll) C++17
100 / 100
 1824 ms 18736 KB 
#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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 250 ms 18620 KB Output is correct
8 Correct 255 ms 18704 KB Output is correct
9 Correct 262 ms 18700 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 250 ms 18620 KB Output is correct
8 Correct 255 ms 18704 KB Output is correct
9 Correct 262 ms 18700 KB Output is correct
10 Correct 1402 ms 18656 KB Output is correct
11 Correct 1791 ms 18648 KB Output is correct
12 Correct 1824 ms 18736 KB Output is correct