首页技术正文

[题解]UVA10054 The Necklace

开发者芸硕技术 2022年11月17日

0 收藏 972 点赞 4,135 浏览 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 }