Educatinal CF #122(Div. 2) E . Spanning Tree Queries

这一场其实有重大的意义，因为是除夕跨年，不过我FST掉大分了(ks）

题意：给你一个n点，m条边的带权图，q次询问，每次给你\(x\),每个边权为\(abs(E[i].w-x)\)答案为所有询问最小生成树边权和。然后输出所有询问结果的异或和。
思路：

因为\(n(n<=50),m(m<=300)\)很小。而\(k(k<=10^7)\)又很大。所以肯定不能每个询问直接求，这里是把询问的x，分块预处理。

如果有两条边\(w1,w2(w1<w2)\)选1条，原来最小生成树，选边一定选w1,但仔细考虑绝对值情况下，也就只有两种情况:令\(mid=\frac{w1+w2}{2}\)。当\(x<mid\)，就选\(w1\),当\(x=mid\)都可以，当\(x>mid\)选\(w2\)，所以\(mid\)的感觉就像一个分解线

因此我们排序且离散化出任意两条边的\(mid\)。对于每个\(mid\)求其最小生成树，存入sum[mid]。当\(x\)属于\([mid[i],mid[i+1])\)之间就可以用这个值。[因为mid实际求的时候用的上取整]

不过我们只求了\(x=mid\)时的mnsum,范围内其它的怎么求呢？

发现如果我们再在\(mid[]\)集合中加入每个边权。发现每个块内每条选的边的权值都是会随着x++，对mnsum=+1/-1的。

证明：如果上面条件不满足，那么一定存在一个边权在(mid[i],mid[i+1])

然而\(mid[]\)包含所有边权，矛盾。

所以处理出dta[mid]表示x++,mnsum的变化。

最后询问的时候二分一下在哪个块。

ps.注意一下边权排序的时候abs相等时，优先选对dta贡献大的（即边权）大的。
code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=55;

const int M=305;

struct edge {int qs,x,y;ll z;}E[M],A[M];

bool cmp(edge u,edge v) {return u.z==v.z?u.qs<v.qs:u.z<v.z;}

ll sum[M*M],val[M*M];

int cv,tot,fa[N],dta[M*M];

int g_fa(int u) {return fa[u]==u?u:fa[u]=g_fa(fa[u]);}

int main() {

	int n,m;

	scanf("%d%d",&n,&m);

	val[++tot]=0;val[++tot]=1e8+1;

	for(int i=1;i<=m;i++) {scanf("%d%d%lld",&A[i].x,&A[i].y,&A[i].z);val[++tot]=A[i].z;}

	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++)val[++tot]=(A[i].z+A[j].z+1)>>1;

	sort(val+1,val+1+tot);

	cv=unique(val+1,val+1+tot)-val-1;

	for(int j=1;j<=cv;j++) {

		for(int i=1;i<=n;i++)fa[i]=i;

		for(int i=1;i<=m;i++) E[i]=(edge){(A[i].z>val[j])?-1:1,A[i].x,A[i].y,abs(A[i].z-val[j])};

		sort(E+1,E+1+m,cmp);

		for(int i=1,t=1;i<=m&&t<n;i++) {

			int u=g_fa(E[i].x),v=g_fa(E[i].y);

			if(u==v)continue;

			fa[u]=v;

			sum[j]+=E[i].z;dta[j]+=E[i].qs;t++;

		}

	}

	ll xos=0,x;

	int p,k,a,b,c;scanf("%d%d%d%d%d",&p,&k,&a,&b,&c);

	for(int i=1;i<=k;i++) {

		if(i<=p) scanf("%lld",&x);

		else x=(x*a+b)%c;

		int y=upper_bound(val+1,val+1+cv,x)-val-1;

		ll res=sum[y]+1ll*dta[y]*(x-val[y]);

		xos^=res;

	}

	printf("%lld",xos);

	return 0;

}

巴特西

Educatinal CF #122(Div. 2) E . Spanning Tree Queries

最新文章

热门文章