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

二分图、拓扑与欧拉

1、二分图匹配问题(判断是否二分图可以使用并查集)
`// 邻接表存储图
int n1, n2, m;
int h[500], e[100010],ne[100010], idx = 0;
//st 标记是否递归找过, match[x]:和 x 编号的男生的编号
int st[510], match[510];
//存图函数
void add(int a, int b){
e[idx] = b, ne[idx] = h[a]; h[a] = idx++;
}
//递归找可以匹配的点
bool find(int x){
// 和各个点尝试能否匹配
for(int i = h[x]; i != -1; i = ne[i]){
int b = e[i];
if(!st[b]){//打标记
st[b] = 1;
// 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配
if(match[b] == 0 || find(match[b])){
// 和当前尝试点匹配在一起
match[b] = x;
return true;
}
}
}
return false;
}

int main(){
memset(h, -1, sizeof h);
cin >> n1 >> n2 >> m;
// 保存图,因为只从一遍找另一边,所以该无向图只需要存储一个方向
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
//为各个点找匹配
for(int i = 1; i <= n1; i++){
memset(st, 0, sizeof st);
//找到匹配
if(find(i)) res++;
}
cout << res;
return 0;
}`

2、拓扑排序(核心在出度和入度,相当于bfs思路,常用于有多重先后顺序的点排列)(下面的例题用于求取所有起点出发到所有终点的总路径,拓扑在此并非用于‘求’排列,而是‘维护’题意的排列并求路径)
`const int MOD = 80112002;
int n, m; // n: 节点数, m: 边数
int rudu[5010];int chudu[5010];// 每个点的出度入度
int sg[5010]; // 标记数组,记录是否已入队
int dp[5010]; // dp[i]: 从任意起点到达i的路径数
int ans = 0;

// cb[x]: 从x出发的所有“反向边”目标(即图的反向边存储)
// rb[x]: 正向边的邻接表(可选)
unordered_map<int, vector> cb;
unordered_map<int, vector> rb;

void tppx() {
queue q;
for (int i = 1; i <= n; i++) {
if (rudu[i] == 0) {
q.push(i);// 初始化:所有入度为0的点是起点
dp[i] = 1;// 起点到自身路径数 = 1
sg[i] = 1;
}
}

// BFS式拓扑排序
while (!q.empty()) {int up = q.front(); q.pop();// 遍历up的所有后继节点(反向存储时要注意方向)for (int i = 0; i < cb[up].size(); i++) {int v = cb[up][i];rudu[v]--;  // 消去一条入度// 动态规划转移:dp[v] += dp[up]dp[v] = (dp[v] + dp[up]) % MOD;}for (int i = 1; i <= n; i++) {if (rudu[i] == 0 && !sg[i]) {q.push(i);sg[i] = 1;// 入度归0的点入队}}
}//如果要判断可否拓扑排序,这里可以加一个if,判断是否所有点sg都记录为已经入队过

}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int A, B; cin >> A >> B;
// 注意这里边是 B -> A (存反向图) 因为作者的dp计算方向是反向的
rudu[A]++; // A 的入度 +1
cb[B].push_back(A); // 记录反向边 B -> A
rb[A].push_back(B); // 记录正向边 A -> B
chudu[B]++; // B 的出度 +1
}

tppx();
for (int i = 1; i <= n; i++) {if (chudu[i] == 0) {ans = (ans + dp[i]) % MOD;// 所有出度为0的节点都是“终点”,记录到它们的所有路径}
}cout << ans << endl;
return 0;

}`

http://www.hskmm.com/?act=detail&tid=31830

相关文章:

  • pytorch作业
  • pytorch实验题作业
  • 每日笔记
  • Zhengrui #3346. DINO
  • Pytorch深度学习训练
  • P11894 「LAOI-9」Update
  • ZR 2025 NOIP 二十连测 Day 3
  • 读书报告
  • P14223 [ICPC 2024 Kunming I] 乐观向上
  • 别再用均值填充了!MICE算法教你正确处理缺失数据
  • 非主流网站程序IndexNow添加方法
  • 卷积神经网络视频读书报告
  • C 语言 - 内存操作函数以及字符串操作函数解析
  • 以*this返回局部对象的两种情况
  • 2025.10.15
  • 软件开发流程
  • Kali 自定义ISO镜像
  • 2025秋_12
  • 10月15日
  • 第七章:C控制语句:分支和跳转
  • 感知节点@5@ ESP32+arduino+ 第三个程序FreeRTOS 上 LED灯显示 和 串口打印ASCII表
  • pytorch实训题
  • 数据库基础知识1
  • 近期模拟赛汇总
  • 实用指南:部署Tomcat11.0.11(Kylinv10sp3、Ubuntu2204、Rocky9.3)
  • Hbase的安装与配置
  • 【Azure App Service】App Service是否支持PHP的版本选择呢?
  • OAuth/OpenID Connect 渗透测试完全指南
  • Problem K. 置换环(The ICPC online 2025)思路解析 - tsunchi
  • Go 语言和 Tesseract OCR 识别英文数字验证码