当前位置: 首页 > news >正文

赛前训练3 欧拉路

以下,斜体表示注意点,粗体表示技巧点。

无向图欧拉路径的判定:

  • 除去孤点之外图联通

  • 度数为奇数的点只有 \(0\)\(2\) 个。

有向图欧拉路径的判定:

  • 除去孤点之外图联通。

  • 出度比入度大一或入度比出度大一的有 \(0\)\(2\) 个。

  • 除了第二条中的点,全都是入度等于出度的点

A

拆边空间大小翻倍

将每条边拆成两条,然后跑有向图欧拉路径即可。

实现
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e4+5;
int n,m,cnt;
int ans[N*10];
vector<int> G[N];void dfs(int cur){for(int &i:G[cur]){if(i){int x=i; i=0;dfs(x);}}ans[++cnt]=cur;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,u,v;i<=m;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}cnt=0,dfs(1);for(int i=cnt;i>=1;i--)cout<<ans[i]<<'\n';return 0;
}

B

判孤点

对于每个连通块,累加其贡献,即连通块中度数为奇数点的个数的一半,孤点和没有奇数点的情况不算。

实现
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=2e5+5;
int n,m,cnt,siz;
int d[N],dfn[N];
vector<int> G[N];void dfs(int cur){if(d[cur]&1)cnt++;dfn[cur]=1,siz++;for(int i:G[cur])if(!dfn[i])dfs(i);
}
void solve(){for(int i=1;i<=n;i++)G[i].clear(),d[i]=dfn[i]=0;for(int i=1,u,v;i<=m;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u); d[u]++,d[v]++;}if(!m){cout<<"0\n";return;}int ans=0;for(int i=1;i<=n;i++){if(!dfn[i]){cnt=siz=0,dfs(i);if(siz>1)ans+=1+(cnt>2?(cnt-2)/2:0);}}cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);for(;cin>>n>>m;solve());return 0;
}

C

仍然考虑拆边,于是题目转化为边翻倍之后有多少种方案使得删掉两条边后仍具有欧拉回路。

删掉两条边理论上会增加四个奇数点,但可以删掉共点的边,这一部分贡献是 \(\sum \operatorname{C}^2_{d_i}\)\(d_i\) 为点 \(i\) 的度数)。

注意到这题有自环,于是我们可以选两个不同的自环,贡献为 \(\operatorname{C}^2_{tot}\)\(tot\) 为自环个数);也可以选一个自环和一个普通边,贡献为 \(tot \times (m-tot)\)

实现
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=2e6+5;
int n,m;
int d[N],fa[N];
bool vis[N];int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;int tot=0;for(int i=1,u,v;i<=m;i++){cin>>u>>v;vis[u]=vis[v]=1;if(u==v){tot++;continue;}d[u]++,d[v]++;u=fnd(u),v=fnd(v);if(u!=v)fa[u]=v;}int root=0;for(int i=1;i<=n;i++)if(fa[i]==i&&vis[i])root++;if(root>1){cout<<0;return 0;}int ans=tot*(tot-1)/2+tot*(m-tot);for(int i=1;i<=n;i++)ans+=d[i]*(d[i]-1)/2;cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=12167

相关文章:

  • SQL小贴式: 用NOT EXISTS 而不是 NOT IN !!!
  • 手撕大模型|FlashAttention 原理及代码解析
  • react工程化
  • CF700E Cool Slogans 做题记录
  • 完整教程:在 Ubuntu 上安装和配置 PostgreSQL 实录
  • 一个MCU与FPGA混合电路上电启动的问题及其解决办法探索[原创www.cnblogs.com/helesheng]
  • JMX与RMI
  • 通过主机监控发现路径遍历漏洞的实战技巧
  • Code New Roman 字体的正确下载方式
  • 多态是对于处理不同的变量,但是使用相同或者类似的方式。多态核心分为两种形式:编译时多态(静态多态)和运行时多态(动态多态)C++中多态通常使用虚函数或者指针(引用)实现。
  • 从 C++ 到 Python
  • Nipper 3.9.0 for Windows Linux - 网络设备漏洞评估
  • c++单例实践
  • NOIP 模拟赛九
  • 个人项目-软件工程第二次作业 - Nyanya-
  • 详细介绍:互联网医院品牌IP的用户体验和生态构建
  • 支持 SSL 中等强度密码组(SWEET32) - 漏洞检查与修复
  • C# WPF CommunityToolkit.MVVM (测试一)
  • linux kernel synchronization rcu
  • 锁定Nvidia驱动版本
  • 第二十一章-sql 注入-union 联合注入 (1)
  • Android开发参考
  • 求出e的值
  • 线段树
  • CSP-S模拟24
  • 今年CSP...
  • 0voice-2.1.1-io多路复用select/poll/epoll
  • Transformer与ViT
  • comfUI背后的技术——VAE - 实践
  • CCPC2023 秦皇岛 M. Inverted