【UVa 10054】欧拉回路

2019-11-08 03:07:24

字体：大中小

来源：转载

供稿：网友

题目链接：

UVa-10054

题目大意：

给一串珠子，每个珠子由两半组成，每半颜色不同，珠子只有接触的地方颜色相同才能连接。给一串珠子，问能不能串起来。

题解：

这题不是很好想，我在数学课上想了五分钟，还是忍不住翻书看题解。。。这题的做法是将颜色看做结点，没有一个珠子，就将两半颜色之间连一根线，若是珠子能连接起来，就是说明这个图有一个欧拉回路。而对无向图欧拉回路的判断，就是看每个点的度是不是偶数，可以在线性的时间内做出判断。（这题是不是展示了数学建模的重要性）最后对路径的输出还要小心一点，具体可看我的代码：

代码：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 55#define fill(a,x) memset(a,x,sizeof(a))int map[N][N];int sc[N];void work(int u){ for(int v = 1;v <= 50;v++) if(map[u][v]) { map[u][v]--; map[v][u]--; work(v); PRintf("%d %d/n",v,u); }}int main(){ int t,n,u,v; scanf("%d",&t); for(int kase = 1;kase <= t;kase ++) { scanf("%d",&n); fill(map,0); fill(sc,0); for(int i = 1;i <= n;i++) { scanf("%d%d",&u,&v); map[u][v] ++; map[v][u] ++; sc[u] ++; sc[v] ++; } printf("Case #%d/n",kase); int i; for(i = 1;i <= 50;i++) if(sc[i] % 2 != 0) break; if(i <= 50) printf("some beads may be lost/n"); else for(int i = 1;i <= 50;i++) work(i); if(kase != t) printf("/n"); } return 0;}

上一篇：Linux基础命令详解

下一篇：UVA 679 Dropping Balls (二叉树的编号)