제출 #586811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586811		1ne	Toll (APIO13_toll)	C++14	16 / 100	1 ms	212 KiB

toll

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,cost;
};
struct DSU{
	vector<long long>parent,sz;
	//vector<pair<long long,long long>>ops;
	set<pair<long long,long long>>new_edge;
	vector<vector<pair<long long,long long>>>adj;
	vector<vector<long long>>comp;
	vector<long long>maxxy;
	vector<vector<node>>pos;
	void build(long long n){
		parent.resize(n);
		sz.resize(n);
		adj.resize(n);
		comp.resize(n);
		maxxy.resize(n);
		for (long long i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
			maxxy[i] = 0;
			comp[i].push_back(i);
		}
	}
	void add_edge(long long u,long long v){
		new_edge.insert({max(u,v),min(u,v)});
	}
	long long findsets(long long v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(long long a,long long b,long long cost){
		long long u = findsets(a);
		long long v = findsets(b);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		int counts = 0;
		for (auto x:comp[u]){
			for (auto y:comp[v]){
				if (new_edge.find({max(x,y),min(x,y)})!=new_edge.end()){
					if (counts == 0){
						pos.emplace_back();
					}
					pos.back().push_back({x,y,cost});
					counts++;
					new_edge.erase({max(x,y),min(x,y)});
				}
			}
		}
		if (counts==0){
			adj[a].push_back({b,0});
			adj[b].push_back({a,0});
		}
		//ops.push_back({v,parent[v]});
		parent[v] = u;
		//ops.push_back({~u,sz[u]});
		sz[u]+=sz[v];
		maxxy[u] = max(maxxy[u],maxxy[v]);
		comp[u].insert(comp[u].end(),comp[v].begin(),comp[v].end());
		comp[v].clear();
		return true;
	}
	/*void roll_back(long long v){
		while((long long)ops.size() > v){
			long long i = ops.back().first;
			long long j = ops.back().second;
			ops.pop_back();
			if (i >= 0){
				parent[i] = j;
			}
			else{
				sz[~i] = j;
			}
		}
	}
	*/
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,m,k;cin>>n>>m>>k;
	vector<node>edge(m);
	for (long long i = 0;i<m;++i){
		long long x,y,cost;
		cin>>x>>y>>cost;
		--x;
		--y;
		edge.push_back({x,y,cost});
	}
	sort(edge.begin(),edge.end(),[&](auto x,auto y){
		return x.cost < y.cost;
	});
	DSU st;
	st.build(n);
	for (long long i = 0;i<k;++i){
		long long x,y;cin>>x>>y;
		--x;
		--y;
		st.add_edge(x,y);
	}
	vector<long long>p(n);
	for (long long i = 0;i<n;++i)cin>>p[i];
	for (auto x:edge){
		st.unionset(x.x,x.y,x.cost);
	}
	const int mxn = 1e9;
	auto getmaxx =[&](){
		vector<long long>dist(n,mxn);
		dist[0] = 0;
		queue<int>q;
		q.push(0);
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:st.adj[u]){
				if (dist[x.first] > dist[u] + x.second){
					dist[x.first] = dist[u] + x.second;
					q.push(x.first);
				}
			}
		}
		long long ans = 0;
		for (int i = 0;i<n;++i){
			ans+=dist[i] * p[i];
		}
		return ans;
	};
	long long ans = 0;
	function<void(int)>solve = [&](int u){
		if (u == -1){
			ans = max(ans,getmaxx());
			return;
		}
		for (auto x:st.pos[u]){
			st.adj[x.x].push_back({x.y,x.cost});
			st.adj[x.y].push_back({x.x,x.cost});
			solve(u - 1);
			st.adj[x.x].pop_back();
			st.adj[x.y].pop_back();
		}
	};
	solve((int)st.pos.size() - 1);
	cout<<ans<<'\n';
	return 0;
}
/*
5 5 1
3 5 2 
1 2 3
2 3 5
2 4 4
4 3 6
5 4
10 20 30 40 50
*/

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