E. Cross Swapping

在这里插入图片描述

Example

input

Copy

output

Copy

题解：

通过观察可以发现对于g[i][j]只能和g[j][i]互相换位置。因此对于g[i][j]和g[j][i]的位置进行贪心讨论。从头开始逐行扫描，如果g[i][j]则需要交换，因此需要对操作i和操作j种正好一个操作一次。如果不需要换位置，那么i操作和j操作要么一个都没做，要么全都做了。

 
这个剩下的就是带扩展域的并查集的模板题了。 
const int N=1000010,M=N*2,mod=1e9+7;
int n,m,k,a[N];
int g[1010][1010];
int fa[N],vis[N],w[N];

int find(int x){
	if(fa[x]!=x){
		int p=find(fa[x]);
		w[x] ^= w[fa[x]];
		fa[x]=p;
	}
	return fa[x];
}

void solve(){
	n=read();
	rep(i,1,n) fa[i]=i,w[i]=0;
	rep(i,1,n) rep(j,1,n) 
		g[i][j]=read();
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(g[i][j]<g[j][i]){
				int pi=find(i),pj=find(j);
				if(pi!=pj){
					fa[pi]=pj;
					w[pi]=w[i]^w[j];
				}
			}
			else if(g[i][j]>g[j][i]){
				int pi=find(i),pj=find(j);
				if(pi!=pj){
					fa[pi]=pj;
					w[pi]=w[i]^w[j]^1;
				}
			}
		}
	}
	
	rep(i,1,n) {
		find(i);
		if(w[i])
			rep(j,1,n) swap(g[i][j], g[j][i]);
	}
	
	for(int i=1;i<=n;i++)
            for(int j=1;j <= n;j++)
                cout << g[i][j] << " \n"[j == n];
}
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



                

                    相关阅读:

                    
flutter开发实战-自定义长按TextField输入框剪切、复制、选择全部菜单AdaptiveTextSelectionToolba样式UI效果                            

支持多校 微信课表小程序源码 排课小程序源码 支持导入课表 情侣课表 背景设置                            

第四章字符串_反转字符串里的单词                            

SpringBoot请求参数与响应返回值,ResponseEntity＜T＞自定义响应                            

牛客算法题：B-装进肚子                            

对max2900的一些了解                            

常用的基本命令（必掌握）                            

【React学习】—React简介（一）                            

一分钟禁用云服务器root用户改用自定义用户                            

ROCKET PROPULSION ELEMENTS——DEFINITIONS AND FUNDAMENTALS笔记                            

                    
                
                
                    原文地址：https://blog.csdn.net/m0_51780913/article/details/126337173