CF603E Pastoral Oddities

本文主要是介绍CF603E Pastoral Oddities，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF603E Pastoral Oddities

给定一张 \(n\) 个点的无向图，初始没有边。

依次加入 \(m\) 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。

若存在，则还需要最小化边集中的最大边权。

\(n \le 10^5,m \le 3 \times 10^5\)。

首先观察题目条件，发现 \(n\) 的大小必须要是偶数。

接着容易发现其实如果两个连通块大小都是偶数，他们之间的边不用连接。

这样一步步寻找可以将题目条件转化为：整张图的所有连通块大小都为偶数。

那么现在需要每次加入一条边，对这张图做最小生成树。

显然暴力做需要 LCT 珂姬，而在线基本上就是行不通，会想到将所有边离线下来处理。

那么按照边权从小到大枚举，观察答案发现随着加入更多的边，答案一定不会增大。

这里向下容易掉进一个二分的坑中，对每条边二分一个最靠前的、满足条件的时间点，加入这条边。但其实在查询一个二分值的时候可能会有 \(\mathcal{O(n)}\) 的复杂度，难以接受。

看看从小到大枚举每条边时我们的操作：如果二分到一个可行的时间点，那这个时间点以后的所有位置都不再需要考虑，并在剩余的位置加入这条边，这样成功的次数不超过 \(m\) 次，为什么不直接从大到小枚举每个时间点，尝试加入新的边直到这个时间点满足条件？（如果不满足条件再往前的都不会满足条件）

这样需要一个数据结构支持在时间区间加入一条边、单点查询。这不就是线段树分治吗？

那在线段树分治中先右再左递归询问，如果到达了一个叶子节点就尝试加入新的边，直到这个时间点满足条件。

其中有个细节就是加入一条边的时候可能会加到自己这个节点上，那就添加的时候添加到 \([l,r)\) 的位置，将当前时间轴跳过即可。

#define Maxn 100005
#define Maxm 300005
int n,m,tp,Left,used,nowans;
int fa[Maxn],siz[Maxn],ans[Maxm];
pa sta[Maxm];
struct EDGE
{
	int l,r,u,v,val;
	EDGE(int L=0,int R=-1,int U=0,int V=0,int Val=0):
		l(L),r(R),u(U),v(V),val(Val){}
	inline friend bool operator < (EDGE x,EDGE y) { return x.val<y.val; }
}e[Maxm];
vector<int> tree[Maxm<<2];
int Find(int x){ return (fa[x]==x)?x:Find(fa[x]); }
inline void merge(int x,int y)
{
	x=Find(x),y=Find(y);
	if(x==y) return;
	if(siz[x]>siz[y]) swap(x,y);
	Left-=(siz[x]&1)+(siz[y]&1);
	sta[++tp]=pa(x,y),fa[x]=y,siz[y]+=siz[x];
	Left+=siz[y]&1;
}
void addedge(int p,int nl,int nr,int l,int r,int x)
{
	if(nl>=l && nr<=r) { tree[p].pb(x); return; }
	int mid=(nl+nr)>>1;
	if(mid>=l) addedge(p<<1,nl,mid,l,r,x);
	if(mid<r) addedge(p<<1|1,mid+1,nr,l,r,x);
}
void solve(int p,int nl,int nr)
{
	int Intp=tp,mid=(nl+nr)>>1;
	for(int i:tree[p]) merge(e[i].u,e[i].v);
	if(nl==nr)
	{
		for(;Left && used<=m;used++)
		{
			if(e[used].l>nl) continue;
			merge(e[used].u,e[used].v),nowans=e[used].val;
			if(e[used].l<nl) addedge(1,1,m,e[used].l,nl-1,used);
		}
		if(!Left) ans[nl]=nowans;
		else ans[nl]=-1;
	}
	else solve(p<<1|1,mid+1,nr),solve(p<<1,nl,mid);
	while(tp>Intp)
	{
		int x=sta[tp].fi,y=sta[tp].se;
		Left-=siz[y]&1,fa[x]=x,siz[y]-=siz[x];
		Left+=(siz[x]&1)+(siz[y]&1),tp--;
	}
}
int main()
{
	Left=n=rd(),m=rd();
	for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	for(int i=1,u,v,d;i<=m;i++)
		u=rd(),v=rd(),d=rd(),e[i]=EDGE(i,-1,u,v,d);
	sort(e+1,e+m+1),solve(1,1,m);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

这篇关于CF603E Pastoral Oddities的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！