首页 技术 正文
技术 2022年11月17日
0 收藏 972 点赞 4,134 浏览 1142 个字

链接:http://vjudge.net/problem/viewProblem.action?id=18806

描述:给出一堆珠子,每个珠子有两种颜色,有一端颜色相同的珠子可以串在一起,问是否可以把所有珠子串在一起,并求其中一种方案。

思路:欧拉回路

以颜色作为节点,以珠子作为边建图,无向图。

下面是我的实现:

 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 #define MaxC 55
6 int Edge[MaxC][MaxC],Du[MaxC];
7 int M,Cnt;
8 bool vis[MaxC][MaxC];
9 inline void Addedge(int u,int v)
10 {
11 Edge[u][v]++;Edge[v][u]++;
12 }
13 void Solve(int u)
14 {
15 int v;
16 for(v=1;v<=M;)
17 {
18 if(Edge[u][v])
19 {
20 // vis[u][v]=vis[v][u]=1;
21 Edge[u][v]--;Edge[v][u]--;
22 Solve(v);
23 printf("%d %d",v,u);
24 if(u!=M)
25 printf("\n");
26 if(u==M)
27 {
28 Cnt--;
29 if(Cnt)
30 printf("\n");
31 }
32 }
33 else v++;
34 }
35 }
36 int main()
37 {
38 int T,N;
39 int i,j,u,v;
40 scanf("%d",&T);
41 for(i=1;i<=T;i++)
42 {
43 if(i>1) printf("\n");
44 printf("Case #%d\n",i);
45 scanf("%d",&N);
46 memset(Du,0,sizeof(Du));
47 memset(Edge,0,sizeof(Edge));
48 memset(vis,0,sizeof(vis));
49 M=0;
50 for(j=1;j<=N;j++)
51 {
52 scanf("%d%d",&u,&v);
53 Addedge(u,v);
54 Du[u]++;Du[v]++;
55 if(M<u) M=u;
56 if(M<v) M=v;
57 }
58 for(j=1;j<=M;j++)
59 if(Du[j]%2)
60 break;
61 if(j<=M)
62 {
63 printf("some beads may be lost\n");
64 continue;
65 }
66 Cnt=Du[M];
67 Solve(M);
68 }
69 return 0;
70 }

给一个我写的数据生成器:http://www.cnblogs.com/CQBZOIer-zyy/p/3818078.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,075
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,551
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,399
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,176
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,811
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,893