欧拉回路（混合图的欧拉回路）-Linux大棚

admin 管理员组

文章数量: 1087649

欧拉回路（混合图的欧拉回路）

/* ID: linjd821 LANG: C++ TASK: sightseeing */ //zju 1992 //混合图的欧拉回路，用网络流调整无向边 /* //转自某位牛人blog 混合图欧拉回路原来混合图欧拉回路用的是网络流。把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。所以，就这样，混合图欧拉回路问题，解了。 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <assert.h> #include <ctype.h> #include <map> #include <string> #include <set> #include <bitset> #include <utility> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <iostream> #include <fstream> #include <list>using namespace std;const int MAXN = 210; const int MAXM = 3100; const int INF = 1000000000;struct Edge {int st, ed;int next;int flow; }edge[MAXM]; int head[MAXN], d[MAXN]; int in[MAXN], out[MAXN];int N, M, E, src, dest;void Init(int s, int t) {E = 0;src = s;dest = t;memset(head, -1, sizeof(head));memset(in, 0, sizeof(in));memset(out, 0, sizeof(out)); }void add_edge(int u, int v, int w1, int w2) {edge[E].st = u; edge[E].ed = v;edge[E].flow = w1; edge[E].next = head[u];head[u] = E++;edge[E].st = v; edge[E].ed = u;edge[E].flow = w2; edge[E].next = head[v];head[v] = E++; }bool dinic_bfs() {int i, j;memset(d, -1, sizeof(d));int que[MAXN], rear = 1;que[0] = src; d[src] = 0;for(i = 0; i < rear; i++)for(j = head[que[i]]; j != -1; j = edge[j].next)if(d[edge[j].ed] == -1 && edge[j].flow > 0){d[edge[j].ed] = d[que[i]]+1;que[rear++] = edge[j].ed;}return d[dest] >= 0; }int dinic_dfs() {int stk[MAXN], top = 0;int ans = 0, cur, ptr, pre[MAXN], minf, i;bool del[MAXN];memset(del, false, sizeof(del));stk[top++] = 0; pre[src] = 0; cur = src;while(top){while(cur != dest && top){for(i = head[cur]; i != -1; i = edge[i].next){if(d[edge[i].ed] == d[cur]+1 && edge[i].flow > 0 && !del[edge[i].ed]){stk[top++] = edge[i].ed;cur = edge[i].ed;pre[edge[i].ed] = i;break;}}if(i == -1){del[cur] = 1;top--;if(top) cur = stk[top-1];}}//update the flowif(cur == dest){minf = INF;while(cur != src){cur = pre[cur];if(edge[cur].flow < minf) minf = edge[cur].flow;cur = edge[cur].st;}cur = dest;while(cur != src){cur = pre[cur];edge[cur].flow -= minf;edge[cur^1].flow += minf;if(edge[cur].flow == 0) ptr = edge[cur].st;cur = edge[cur].st;}while(top > 0&& stk[top-1] != ptr) top--;if(top) cur = stk[top-1];ans += minf;}}return ans;} int Dinic() {int ans = 0, t;while(dinic_bfs()){t = dinic_dfs();if(t) ans += t;else break;}return ans; }int main() {int T;int i, j, u, v, tag, sum;//freopen("g.in", "r", stdin);//freopen("gg.out", "w", stdout);scanf("%d", &T);while(T--){scanf("%d %d", &N, &M);Init(0, N+1);//printf("%d %d", N, M);for(i = 0; i < M; i++){scanf("%d %d %d", &u, &v, &tag);if(u == v) continue;in[v]++; out[u]++;if(tag == 0) add_edge(u, v, 1, 0);}for(i = 1, sum = 0; i <= N; i++){out[i] -= in[i];if(out[i]&1) break;out[i] >>= 1;if(out[i] > 0){add_edge(0, i, out[i], 0);sum += out[i];}else if(out[i] < 0){add_edge(i, N+1, -out[i], 0);}}N++;if(i == N && sum == Dinic()) puts("possible");else puts("impossible");}return 0; }

/* 无向图的欧拉回路（有向图基本上一样）回溯找欧拉回路对于规模比较大的图，可以采用并差集判断连通性题目：USACO Training Page 3.3.1 Riding The Fencespku 2513 =2513 Trie+并差集判断欧拉路径的存在性 */ #include <stdio.h> #include <string.h>const int MAXN = 500+5; //N个点，M条边，1为最小节点 int N, M; int g[MAXN][MAXN], du[MAXN]; //保存最后的路径，逆序输出字典序最小 int path[MAXN], plen; //初始化图和degree void Init() {memset(du, 0, sizeof(du));memset(g, 0, sizeof(g)); } //判断欧拉路径是否存在 bool EulerTour() {int i, j;//度数都为偶数，欧拉回路；有两个点为奇数欧拉路径 for(i = 1, j = 0; i <= N && j <= 2; i++)if(du[i]%2 == 1) j++;if(j != 0 && j != 2) return 0;//判断连通性, BFSint rear = 1, que[MAXN];bool used[MAXN];memset(used, 0, sizeof(used));que[0] = 1; used[1] = true; for(i = 0; i < rear; i++)for(j = 1; j <= N; j++) if(!used[j] && g[que[i]][j]){used[j] = 1;que[rear++] = j;}return rear == N; }void Tour(int t) {int i;for(i = 1; i <= N; i++)if(g[t][i] > 0){g[t][i]--; g[i][t]--;Tour(i);}path[plen++] = t; } //t为欧拉路径的起点 void Show_Euler(int t) {int i;plen = 0;Tour(t);for(i = plen-1; i >= 0; i--)printf("%d/n", path[i]); } int main() {int i, j, k;while(scanf("%d %d", &N, &M) != EOF){Init(); for(i = 0; i < M; i++){scanf("%d %d", &j, &k);g[j][k]++; g[k][j]++;du[j]++; du[k]++;} if(!EulerTour())puts("No Euler Path Exit");else{for(i = 1; i <= N; i++)if(du[i]%2 == 1) break;if(i >= N+1) Show_Euler(1);else Show_Euler(i);}}return 0; }

waiting。。。。。

本文标签：欧拉回路（混合图的欧拉回路）

版权声明：本文标题：欧拉回路（混合图的欧拉回路）内容由网友自发贡献，该文观点仅代表作者本人，转载请联系作者并注明出处：http://www.roclinux.cn/b/1686635378a20005.html，本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。

Linux大棚 – 不忘初心的技术博客，浮躁时代的安静角落

欧拉回路（混合图的欧拉回路）

欧拉回路（混合图的欧拉回路）

更多相关文章

欧拉回路（混合图的欧拉回路）

发表评论

推荐文章

about javascript onclick foreach function - Stack Overflow

javascript - Why getElementById does not work on elements other than document? - Stack Overflow

javascript - html5 - how to collapsing and expanding for complicated table elements - Stack Overflow

javascript - vue enter transition not working properly - Stack Overflow

荣耀笔记本装Win10系统攻略找对方法很重要！

热门文章

Python dataframe optimization with two variables - Stack Overflow

javascript - Jquery showhide div on dynamic content - Stack Overflow

javascript - How would I create a splash screen in Vue.js? - Stack Overflow

How can I check if the current git branch (down to its merge base) is a proper tree? - Stack Overflow

java - Spark giving error when writing a limited length Column of type Varbinary for Synapse database - Stack Overflow

通过Windows镜像离线升级或修复Win10系统

Win7NVMe固态硬盘驱动：提升Windows 7系统硬盘性能

WSL到Windows,最简单的端口转发配置方案

大模型——Spring Boot 整合 Spring AI 实现项目接入ChatGPT

Qt for Android（b站讯为QT教程）

最新文章

javascript - How do I toggle the readonly attribute of all child element with jquery - Stack Overflow

javascript - Might it be possible to block an entire US state from accessing my site, using PHP? - Stack Overflow

c++ - Is dereferencing std::span::end always undefined? - Stack Overflow

javascript - Delay function execution if it has been called recently - Stack Overflow

javascript - Google Maps Autocomplete List - Stack Overflow

Windows系统更新，显示Windows启动管理器，进去后为重装系统界面的解决方法。

win11登录密码忘记了？别慌！无需重装系统，一个U盘轻松移除！

ThinkBook 16p笔记本系统重装全流程指南

openstack(train)创建网络与虚拟机

Java实现SNMP网络设备MIB信息采集系统设计与源代码分析

Exploring the Finest Accommodations: A Comprehensive Guide to Ruston LA Hotels

The Enchanting Experience of ScaliniTella NYC: A Culinary Gem in the Heart of Manhattan

Exploring the Exquisite Aloft Chicago O'Hare: A Blend of Modern Luxury and Convenience

A Culinary Journey: Discovering the Finest Dining Experiences in Waco, TX

A Culinary Journey: Discovering the Finest Dining Experiences in Athens, GA

Linux大棚 – 不忘初心的技术博客，浮躁时代的安静角落

欧拉回路（混合图的欧拉回路）

欧拉回路（混合图的欧拉回路）

更多相关文章

欧拉回路（混合图的欧拉回路）

发表评论

推荐文章

about javascript onclick foreach function - Stack Overflow

javascript - Why getElementById does not work on elements other than document? - Stack Overflow

javascript - html5 - how to collapsing and expanding for complicated table elements - Stack Overflow

javascript - vue enter transition not working properly - Stack Overflow

荣耀笔记本装Win10系统攻略 找对方法很重要！

热门文章

Python dataframe optimization with two variables - Stack Overflow

javascript - Jquery showhide div on dynamic content - Stack Overflow

javascript - How would I create a splash screen in Vue.js? - Stack Overflow

How can I check if the current git branch (down to its merge base) is a proper tree? - Stack Overflow

java - Spark giving error when writing a limited length Column of type Varbinary for Synapse database - Stack Overflow

通过Windows镜像离线升级或修复Win10系统

Win7NVMe固态硬盘驱动：提升Windows 7系统硬盘性能

WSL到Windows,最简单的端口转发配置方案

大模型——Spring Boot 整合 Spring AI 实现项目接入ChatGPT

Qt for Android（b站讯为QT教程）

最新文章

javascript - How do I toggle the readonly attribute of all child element with jquery - Stack Overflow

javascript - Might it be possible to block an entire US state from accessing my site, using PHP? - Stack Overflow

c++ - Is dereferencing std::span::end always undefined? - Stack Overflow

javascript - Delay function execution if it has been called recently - Stack Overflow

javascript - Google Maps Autocomplete List - Stack Overflow

Windows系统更新，显示Windows启动管理器，进去后为重装系统界面的解决方法。

win11登录密码忘记了？别慌！无需重装系统，一个U盘轻松移除！

ThinkBook 16p笔记本系统重装全流程指南

openstack(train)创建网络与虚拟机

Java实现SNMP网络设备MIB信息采集系统设计与源代码分析

Exploring the Finest Accommodations: A Comprehensive Guide to Ruston LA Hotels

The Enchanting Experience of ScaliniTella NYC: A Culinary Gem in the Heart of Manhattan

Exploring the Exquisite Aloft Chicago O'Hare: A Blend of Modern Luxury and Convenience

A Culinary Journey: Discovering the Finest Dining Experiences in Waco, TX

A Culinary Journey: Discovering the Finest Dining Experiences in Athens, GA

荣耀笔记本装Win10系统攻略找对方法很重要！