首页 > 代码库 > [题解]UVA10054 The Necklace

[题解]UVA10054 The Necklace

2024-07-10 09:27:42   223人阅读

链接：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 }
View Code

 

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


联系
我们