Door man

时间：2021-06-17 00:04:24

poj1300:http://poj.org/problem?id=1300

题意：给你n个房间，房间之间有一些门，房间是按0~~n-进行编号的。然后给出一些房间的之间门，n行，每行的数字表示该们与其它们之间是否有门，而且只表示出比他大的房间号。然后给你一个起点，问你从起点出发，然后经过所有的房间回到0点，房间之间可能有多道门。

题解：题目描述的可能不是很清楚，题目是要求一条欧拉回路。源点是0点，可以从起点到达源点之后，看看能否经过每个房间回到0点。

Door manDoor man
 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int readLine(char *s){

     int L;

     for(L=;(s[L]=getchar())!='\n'&&s[L]!=EOF;L++);

     s[L]=;

     return L;

 }//取出每一行，并且返回串的长度（包括空格）；

 int main(){

     char buf[];

     int i,j,m,n;int door[];

     while(readLine(buf)){

         if(buf[]=='S'){

             sscanf(buf,"%*s%d%d",&m,&n);//读取起点和房间的个数 *%s包第一个字符串吃掉了

             for( i=;i<n;i++)

               door[i]=;//初始化

               int doors=;//记录门的个数

               for(i=;i<n;i++){

                   readLine(buf);//读取一行

                   int k=;//表示从哪一位开始读取

                   while(sscanf(buf+k,"%d",&j)==){

                       doors++;

                       door[i]++;

                       door[j]++;

                       while(buf[k]&&buf[k]==' ')k++;//表示把k移动两位，来读取下一个数

                       while(buf[k]&&buf[k]!=' ')k++;//

                   }

               }

               readLine(buf);//读取END

               int even=;//记录偶度点的个数

               int odd=;//记录奇度点的个数

              for( i=;i<n;i++){

                   if(door[i]%==)even++;

                   else

                   odd++;

              }

           if(odd==&&m==)//如果起点是0并且没有奇度点直接输出

               printf("YES %d\n",doors);

           else if(odd==&&door[m]%==&&m!=&&door[]%==)//如果有两个，分别是起点和0，并且起点不是0

             printf("YES %d\n",doors);

             else

             printf("NO\n");           

         }

        if(!strcmp(buf,"ENDOFINPUT"))break;

     }

   return ;

 }

随机推荐

  1. Backbone&period;js源码分析&lpar;珍藏版&rpar;

    源码分析珍藏,方便下次阅读! // Backbone.js 0.9.2 // (c) 2010-2012 Jeremy Ashkenas, DocumentCloud Inc. // Backbone ...

  2. Binary Tree Vertical Order Traversal

    Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bott ...

  3. python中将字符串转化为本地变量

    var = 123445s= locals()['var']s2=vars()['var'] print s,s2

  4. pyVmomi入门

    简要说明 pyVmomi is the Python SDK for the VMware vSphere API that allows you to manage ESX, ESXi, and v ...

  5. UOJ &num;192 【UR &num;14】 最强跳蚤

    题目链接:最强跳蚤 这道题本来不想写博客的--但是鉴于自己犯了低级错误,还是写篇博客记载一下. 一开始我的想法和题解里面的算法而比较类似,也是先分解质因数,然后用质因子是否出现偶数次来判断当前这个数是 ...

  6. 《团队作业》五小福团队作业--UNO-- LandingDay--降落

    <团队作业>五小福团队作业--UNO-- LandingDay--降落 写在前面 几周的飞行之后,降落之日也如期而至了.在2018年12月19日我们顺利地完成了项目的总结汇报.但是,短暂的 ...

  7. 003-单例OR工厂模式

    单例模式:DbContextFactory.cs using CZBK.ItcastOA.Model; using System; using System.Collections.Generic; ...

  8. HTML5 浏览器支持

    css重置 header, section, footer, aside, nav, main, article, figure { display: block; } 为HTML添加新的元素 &lt ...

  9. ORA-16433 The database must be opened in read write mode故障解决

    转 一.首先删除原有控制文件并新建控制文件 1.找到控制文件位置 SQL> show parameter control_files; NAME TYPE VALUE ------------- ...

  10. 【BZOJ5285】&lbrack;HNOI2018&rsqb;寻宝游戏（神仙题）

    [BZOJ5285][HNOI2018]寻宝游戏(神仙题) 题面 BZOJ 洛谷 题解 既然是二进制按位的运算,显然按位考虑. 发现这样一个关系,如果是\(or\)的话,只要\(or\ 1\),那么无 ...

相关文章