首页 > 代码库 > [题解]UVA10054 The Necklace
[题解]UVA10054 The Necklace
链接: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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。