CF1499G - Graph Coloring

Posted on Edited on In

CF1499G - Graph Coloring

题目大意

有一个二分图， \(m\) 条边，每条边可以选择为+1或者-1，表示两端的点权值 \(a_u,a_v\pm 1\)

最终的权值总和是 \(\sum |a_u|\)

现在要维护一个动态加边操作

每次加边之后动态维护一个最优的方案最小化权值和，输出其 \(\text{Hash}\) 和


分析

容易发现在最优中方案 \(|a_u|\leq 1\)

且一个点 \(a_u=\pm 1\) 当且仅当 \(deg_u \mod 2=1\)

在依次加入每条边的过程中，一旦出现环，显然环上的边经交错染色之后贡献可以忽略

且奇点总是成对地出现，两个成对的奇点能够确定一条路径

我们只需要在动态加边的过程中，维护对于这样奇点的路径以及环的交替染色即可

注意：

一个点可以被多条路径经过，但是在奇点成对地过程中

我们只认为其中一条的端点是它


那么我们在路径两端记录这条路径，每次加入一条边之后，可能产生多条路径的合并

而在实际实现的过程中，并没有必要把环从路径上删除

假设当前得到路径 \(x\rightarrow y\) ，加入一条边 \(y,z\) 且 \(z\) 在 \(x\rightarrow y\) 上

此时，我们直接认为新的路径端点就是 \((x,z)\) 即可

环的部分依然可以保留在路径上，跟随路径进行交替染色而不影响答案

此时操作被简化为了合并两段交替路径（实际上就是在合并欧拉路径）

可以用带权并查集维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int N=4e5+10,P=998244353;

int n1,n2,m,w=1;
int S[N][2],F[N],K[N],D[N];
int Find(int x){
	if(F[x]==x) return F[x];
	int f=F[x]; F[x]=Find(F[x]);
	D[x]^=D[f];
	return F[x];
}

int ans;
void Uni(int x,int y){
	int fx=Find(x),fy=Find(y),d=D[x]^D[y]^1;
	if(fx==fy) return;
	if(d) {
		ans-=S[fx][1],Mod2(ans);
		swap(S[fx][0],S[fx][1]);
		ans+=S[fx][1],Mod1(ans);
		D[fx]=1;
	}
	F[fx]=fy; 
	rep(i,0,1) S[fy][i]+=S[fx][i],Mod1(S[fy][i]);
}
void Add(){
	int x=rd(),y=rd()+n1;
	w*=2,Mod1(w),S[++m][0]=w,F[m]=m;
	if(K[x]<K[y]) swap(x,y);
	if(!K[x]&&!K[y]) K[x]=K[y]=m;
	else if(!K[y]) Uni(K[x],m),K[x]=0,K[y]=m;
	else Uni(K[x],m),Uni(K[y],m),K[x]=K[y]=0;
}

int A[N],C;

int main(){
	n1=rd(),n2=rd();
	rep(_,1,rd()) Add();
	rep(_,1,rd()) {
		if(rd()==1) Add(),printf("%d\n",ans),fflush(stdout);
		else {
			C=0;
			rep(i,1,m) if(Find(i),D[i]==1) A[++C]=i;
			printf("%d\n",C);
			rep(i,1,C) printf("%d ",A[i]);
			puts(""),fflush(stdout);
		}
	}
}