您现在的位置是:首页 > 正文

BZOJ4025 二分图

2024-02-01 02:03:44阅读 2

Problem

BZOJ

Solution

关于二分图的判定,我们可以考虑原图的一个生成树,然后对于所有非树边,我们统计一下奇环个数即可

然后可以用时间线段树,带权并查集维护一下路径上的点的个数,时间复杂度是 O ( m log ⁡ T log ⁡ n ) O(m\log T\log n) O(mlogTlogn)

也可以用lct维护时间最大生成树,注意一下细节即可,时间复杂度是 O ( m log ⁡ n ) O(m\log n) O(mlogn)。(提供一个调试的好方法,在erase那里把那句注释掉的assert加上)

数据比较坑,注意可能会自环,还可能存在边start=end。

Code

//#include <assert.h>
#include <algorithm>
#include <cstdio>
#define rg register
#define pd(x) if(rev[x])pushdown(x);
using namespace std;
typedef long long ll;
const int maxn=300010,INF=0x3f3f3f3f;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    if(f) x=-x;
}
struct STACK{
	int tp,a[maxn];
	inline void clear(){tp=0;}
	inline int top(){return a[tp];}
	inline void push(int x){a[++tp]=x;}
	inline void pop(){tp--;}
};
struct data{
	int u,v,id,op,t;
	bool operator < (const data &b)const{return t<b.t;}
}a[maxn<<1],b[maxn];
struct LCT{
	int val[maxn],ch[maxn][2],f[maxn],rev[maxn],sz[maxn],mn[maxn];
	STACK stk;
	inline int isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}
	void pushup(int x)
	{
		if(val[mn[ch[x][0]]]<val[mn[ch[x][1]]]) mn[x]=mn[ch[x][0]];
		else mn[x]=mn[ch[x][1]];
		if(val[x]<val[mn[x]]) mn[x]=x;
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
	}
	void pushdown(int x)
	{
		rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0;
		swap(ch[x][0],ch[x][1]);
	}
	void rotate(int x)
	{
		int fa=f[x],ff=f[fa],l,r;
		l=(ch[fa][1]==x);r=l^1;
		if(!isroot(fa)){if(ch[ff][0]==fa) ch[ff][0]=x;else ch[ff][1]=x;}
		f[x]=ff;f[fa]=x;f[ch[x][r]]=fa;
		ch[fa][l]=ch[x][r];ch[x][r]=fa;
		pushup(fa);pushup(x);
	}
	void splay(int x)
	{
		stk.clear();stk.push(x);
		for(int i=x;!isroot(i);i=f[i]) stk.push(f[i]);
		for(;stk.tp;stk.pop()) pd(stk.top());
		while(!isroot(x))
		{
			int fa=f[x],ff=f[fa];
			if(!isroot(fa))
			{
				if((ch[fa][0]==x)^(ch[ff][0]==fa)) rotate(x);
				else rotate(fa);
			}
			rotate(x);
		}
	}
	void access(int x){for(int t=0;x;t=x,x=f[x]) splay(x),ch[x][1]=t,pushup(x);}
	void makeroot(int x){access(x);splay(x);rev[x]^=1;}
	int find(int x){access(x);splay(x);while(ch[x][0]) x=ch[x][0];return x;}
	void split(int x,int y)
	{
		makeroot(x);
		access(y);
		splay(y);}
	void cut(int x,int y){split(x,y);if(ch[y][0]==x) ch[y][0]=0,f[x]=0;}
	void link(int x,int y){makeroot(x);f[x]=y;}
}T;
int n,m,t,p=1,cnt,tree[maxn<<1];
void input()
{
	int u,v,s,e;
	read(n);read(m);read(t);
	for(rg int i=0;i<=n;i++) T.val[i]=INF;
	for(rg int i=1;i<=m;i++)
	{
		read(u);read(v);read(s);read(e);
		if(s==e){--i;--m;continue;}
		a[i+i-1]=(data){u,v,i,1,s};a[i<<1]=(data){u,v,i,0,e};
		b[i]=(data){u,v,i,s,e};T.val[n+i]=e;
	}
	m<<=1;sort(a+1,a+m+1);
}
void insert(int id)
{
	if(a[id].u==a[id].v){++cnt;return ;}
	if(T.find(a[id].u)==T.find(a[id].v))
	{
		T.split(a[id].u,a[id].v);
		int num=T.mn[a[id].v]-n,tmp=(T.sz[a[id].v]+1)>>1;
		if(tmp&1) ++cnt;
		if(T.val[num+n]>=b[a[id].id].t) return ;
		T.cut(b[num].u,b[num].id+n);T.cut(b[num].v,b[num].id+n);
		tree[num]=0;
	}
	T.link(a[id].u,a[id].id+n);T.link(a[id].v,a[id].id+n);
	tree[a[id].id]=1;
}
void erase(int id)
{
	if(tree[a[id].id])
	{
		T.cut(a[id].u,a[id].id+n);T.cut(a[id].v,a[id].id+n);
	}
	else
	{
		if(a[id].u==a[id].v){--cnt;return ;}
		//assert(T.find(a[id].u)==T.find(a[id].v));
		T.split(a[id].u,a[id].v);
		int tmp=(T.sz[a[id].v]+1)>>1;
		if(tmp&1) --cnt;
	}
	tree[a[id].id]=0;
}
int main()
{
	input();
	for(rg int i=0;i<t;i++)
	{
		for(;p<=m&&a[p].t<=i;++p)
		{
			if(a[p].op) insert(p);
			else erase(p);
		}
		puts(cnt?"No":"Yes");
	}
	return 0;
}

网站文章

  • 数据结构之稀疏数组

    数据结构之稀疏数组

    目录一、稀疏数组的基本介绍二、稀疏数组的应用场景三、稀疏数组的处理方法四、二维数组转稀疏数组的思路五、稀疏数组转二维数组的思路六、具体代码实现一、稀疏数组的基本介绍当一个数组中大部分元素为0,或者为同...

    2024-02-01 02:03:37
  • 使用MyBatis in查询(单次查询)和for循环查询(多次查询) 的效率问题

    中嵌套子查询语句的情况,确实有这么一回事,但本文不做讨论,因为实际的开发中&quot;关联表查询影响效率的问题&quot;是可以在设计上避免的,而且也应该在设计上避免。语句中不包含子查询,而是确切的一...

    2024-02-01 02:03:02
  • TCP通信转HTTP桥接器(转发zabbix数据为例)

    以zabbix通信转发为例,说明通过HTTP协议转发TCP请求的过程以及相应程序的设计实现与最终效果。

    2024-02-01 02:02:55
  • JAVA递归练习—打印图形

    1. 打印乘法口诀 package cn.oop.program; /** * 打印乘法口诀 * @author 温暖wk * 2018.8.18 */ public class ChengFa { public static void main(String[] args) { System.out.println(&quot;乘法口诀如下:&quot;); f...

    2024-02-01 02:02:46
  • 网络安全专业很吃香?不见得,小白避坑的建议

    网络安全专业很吃香?不见得,小白避坑的建议

    近年来,随着国家对网络安全的战略关注和新基建的持续投入,网络安全专业成为一个热门话题。然而,好专业不一定就能找到好工作,对于想从事网络安全专业的小白们,需要持谨慎态度,避免走一些弯路。一.学习网络安全...

    2024-02-01 02:02:40
  • Spring eureka 启动报错 Error processing condition on org.springframework.cloud.client.loadbalancer.Asyn

    Spring eureka 启动报错 Error processing condition on org.springframework.cloud.client.loadbalancer.Async...

    2024-02-01 02:02:12
  • Redisson分布式限流器RRateLimiter原理解析

    因为公司的开放网关的限流模块就是基于Redisson开发的,之前看的版本源码与最新的已经有很大的不同,趁着整理知识点的机会下了最新版的源码看了一遍。限流这个说简单也简单,说复杂也复杂。不知道是不是我看的东西太少,我觉得redisson的限流器设计非常精巧,感觉把redis玩穿了。

    2024-02-01 02:02:06
  • 【docker】docker部署单机redis

    【代码】【docker】docker部署单机redis。

    2024-02-01 02:01:59
  • echarts实现横轴刻度名倾斜展示,并且解决文字超出部分消失问题 最新发布

    echarts实现横轴刻度名倾斜展示,并且解决文字超出部分消失问题 最新发布

    xAxis.axisLabel. interval如果不手动设值的话,默认就是‘auto’,会采用标签不重叠的策略间隔显示标签。如果要设置刻度名倾斜展示,需要给xAxis.axisLabel.rota...

    2024-02-01 02:01:30
  • 事件之事件对象(event)

    事件之事件对象(event)

    DOM中的事件对象event对象中存在是属性和方法如下表所示:在事件处理程序内部,对象this始终等于currentTarget(事件处理程序注册在这个元素之上),而target只包含事件的实际目标(即实际作出事件处理的元素)。使用方法:event.属性                eg:event.preventDefault();--------取消特定时间的默认事件(写...

    2024-02-01 02:01:24