P3639

提交记录

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+5,M=50;
struct node {
	int u,v,w;
} be[N],nw[N],ch[N];
int f[N],f1[N],pe[N];
bool cmp(node x,node y) {
	return x.w<y.w;
}
int find(int x) {
	return x==f[x]?x:f[x]=find(f[x]);
}
int fd(int x) {
	return x==f1[x]?x:f1[x]=fd(f1[x]);
}
int idx;
int bl[M],cnt,head[M],tt;
struct edge {
	int to,nxt,w;
} e[2*M];
void add(int u,int v) {
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dep[M],fa[M],p[M],p1[M];
void dfs(int u,int fr) {
	dep[u]=dep[fr]+1,fa[u]=fr;
	p[u]=p1[u];
	for(int i=head[u]; i; i=e[i].nxt) {
		if(e[i].to==fr)continue;
		dfs(e[i].to,u);
		p[u]+=p[e[i].to];
	}
}
int sum,ans,vv[M];
void upd(int u,int v,int w) {
//	if(dep[u]<dep[v])swap(u,v);
//	while(dep[u]>dep[v]) {
//		vv[u]=min(vv[u],w);
//		u=fa[u];
//	}
//	while(u!=v) {
//		vv[u]=min(vv[u],w);
//		vv[v]=min(vv[v],w);
//		u=fa[u],v=fa[v];
//	}
	while(u!=v){
		if(dep[u]>dep[v])swap(u,v);
		vv[v]=min(vv[v],w);v=fa[v];
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++)f[i]=i,f1[i]=i;
	for(int i=1; i<=m; i++)cin>>be[i].u>>be[i].v>>be[i].w;
	for(int i=1; i<=k; i++) {
		cin>>nw[i].u>>nw[i].v;
		int a=find(nw[i].u),b=find(nw[i].v);
		if(a!=b)
			f[a]=b;
	}
	for(int i=1; i<=n; i++)
		cin>>pe[i];
	sort(be+1,be+1+m,cmp);
	for(int i=1; i<=m; i++) {
		int a=find(be[i].u),b=find(be[i].v);
		if(a!=b) {
			f[a]=b;
			a=fd(be[i].u),b=fd(be[i].v); 
			if(a<b)swap(a,b);
			f1[a]=b;
		}
	}
	for(int i=1; i<=n; i++) {
		if(f1[i]==i)bl[i]=++idx,p1[idx]=pe[i];
		else {
			int t=fd(i);
			bl[i]=bl[t];
			p1[bl[t]]+=pe[i];
		}
	}

	for(int i=1;i<=m;i++){
		int a=fd(be[i].u),b=fd(be[i].v);
		if(a!=b){
			ch[++tt].u=be[i].u,ch[tt].v=be[i].v,ch[tt].w=be[i].w;
			if(a<b)swap(a,b);f1[a]=b;
		}
	}
	bool ff;
	for(int i=1; i<=(1<<k)-1; i++) {
		memset(vv,0x3f,sizeof(vv));
		memset(head,0,sizeof(head));
		cnt=0;
		memset(fa,0,sizeof(fa));
		memset(dep,0,sizeof(dep));
		for(int j=1; j<=idx; j++)
			f1[j]=j;
		ff=0;
		for(int j=1; j<=k; j++)
			if((i>>(j-1))&1) {
				int a=fd(bl[nw[j].u]),b=fd(bl[nw[j].v]);
				if(a!=b) {
					f1[a]=b;
					add(bl[nw[j].u],bl[nw[j].v]);
					add(bl[nw[j].v],bl[nw[j].u]);
				}else{
					ff=1;break;
				}
			}
		if(ff)continue;
		for(int i=1; i<=tt; i++) {
			int a=fd(bl[ch[i].u]),b=fd(bl[ch[i].v]);
			if(a!=b) {
				f1[a]=b;
				add(bl[ch[i].u],bl[ch[i].v]);
				add(bl[ch[i].v],bl[ch[i].u]);
			}
		}
		dfs(bl[1],0);
		for(int j=1; j<=tt; j++)
			upd(bl[ch[j].u],bl[ch[j].v],ch[j].w);
		sum=0;
		for(int j=1; j<=k; j++)
			if(((i>>(j-1))&1)) {
				int u=bl[nw[j].u],v=bl[nw[j].v];
				if(dep[u]<dep[v])swap(u,v);
				sum+=vv[u]*p[u];
			}
		ans=max(ans,sum);
	}
	cout<<ans;
	return 0;
}

悬赏