注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SGU101[Domino]  

2010-08-24 15:38:59|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

欧拉路。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const int MAXE=100*2;

const int MAXV=6-0+1;

typedef struct struct_edge* edge;

struct struct_edge{int v,id;char dir;edge n;};

struct_edge pool[MAXE];

edge top=pool;

edge adj[MAXV];

int degree[MAXV];

int used[MAXE/2];

int list[MAXE/2+1];

int listtop;

int size[MAXV][MAXV];

edge edges[MAXV][MAXV][MAXE];

int printed[MAXE/2];

void add_edge(int u,int v,int id)

{

     degree[u]++,edges[u][v][size[u][v]++]=top,

     top->v=v,top->id=id,top->dir='+',top->n=adj[u],adj[u]=top++;

     degree[v]++,edges[v][u][size[v][u]++]=top,

     top->v=u,top->id=id,top->dir='-',top->n=adj[v],adj[v]=top++;

}

void find_circuit(int u)

{

     for (edge i=adj[u];i;i=i->n)

         if (!used[i->id])

         {

            used[i->id]=true;

            find_circuit(i->v);

         }

     list[listtop++]=u;

}

void print(int u,int v)

{

     for (int i=0;i<size[u][v];i++)

         if (!printed[edges[u][v][i]->id])

         {

            cout<<edges[u][v][i]->id+1<<" "<<edges[u][v][i]->dir<<endl;

            printed[edges[u][v][i]->id]=true;

            break;

         }

}

 

int main()

{

    int N,a,b;

    cin>>N;

    for (int i=0;i<N;i++)

        cin>>a>>b,add_edge(a,b,i);

    int odc=0;

    int S;

    for (int u=0;u<MAXV;u++)

        if (degree[u])

           S=u;

    #define odd(x) ((x)&1)

    for (int u=0;u<MAXV;u++)

        if (odd(degree[u]))

           odc++,S=u;

    if (odc==0||odc==2)

    {

       find_circuit(S);

       if (listtop==N+1)

          for (int i=1;i<listtop;i++)

              print(list[i-1],list[i]);

       else cout<<"No solution"<<endl;

    }

    else cout<<"No solution"<<endl;

}

 

  评论这张
 
阅读(415)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018