P4826

总的来说，

这道题只考查了单纯的建图和最大生成树

但这却是蓝题（问号

题意

题意的理解比较麻烦

简单说就是 n 支队伍比赛，i 号队伍和 j 号队伍比赛可获得 i ^ j 的分数，然后其中一支队伍会输，退出比赛，问当场上只有一支队伍的时候分数最大是多少

分析

这么看似乎比较麻烦，那我们转化一下：

i 号队伍和 j 号队伍比赛可以看做从 i 向 j 连了一条边，边权就是 i ^ j
其中一支队伍会输，退出比赛，也就是不能出现环
求最大分数也就是在剩下的无环图中找出最大的 n - 1 条边的权值和

证明：

如果可以出现环，那么输掉的球队就可以再次进行比赛，也就是说没有输掉的球队了，而且这样得分也会重复累加

这样我们就可以看出这就是求一个最大生成树的树边和

最后

记得开 long long

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<cmath>

#include<queue>

#include<algorithm>

#define maxn 5005000

using namespace std;

long long n,m,u[maxn],tot,edge_tot,a,b[maxn],cnt;

long long dfn[maxn],low[maxn],sum,ans,head[maxn],fa[maxn];

struct edge{

	long long fr,to,nxt,dis;

}e[maxn*2];

inline void add(long long fr,long long to,long long dis){

	e[++edge_tot].to=to;

	e[edge_tot].dis=dis;

	e[edge_tot].fr=fr;

	e[edge_tot].nxt=head[fr];

	head[fr]=edge_tot;

}

inline long long Get_Father(long long x){

	if(fa[x]==x) return x;

	return fa[x]=Get_Father(fa[x]);

}

inline void ys(long long x,long long y){

	x=Get_Father(x);

	y=Get_Father(y);

	if(x!=y);

	fa[y]=x;

}

inline bool pd(long long x,long long y){

	if(Get_Father(x)==Get_Father(y)) return true;

    else return false;

}

inline long long cp(edge a,edge b){

	return a.dis>b.dis;

}

int main(){

	scanf("%d",&n);

	for(long long i=1;i<=n;i++){

		scanf("%d",&u[i]);

		b[i]=i;

		fa[i]=i;

	}

	for(long long i=1;i<n;i++){

		for(long long j=i+1;j<=n;j++){

			long long c=u[i]^u[j];

			add(i,j,c);

			sum++;

		}

	}

	sort(e+1,e+sum+1,cp);

	for(long long i=1;i<=sum;i++){

//		cout<<e[i].fr<<" "<<e[i].to<<" "<<e[i].dis<<" "<<ans<<endl;

		if(!pd(e[i].fr,e[i].to)){

			ys(e[i].fr,e[i].to);

			ans+=e[i].dis;

			cnt++;

		}

		if(cnt==n-1) break;

	}

	cout<<ans;

	return 0;

}

制作不易，不喜勿喷

巴特西

P4826

题意

分析

证明：

最新文章

热门文章