POJ–1300–Door Man【推断无向图欧拉通路】

POJ–1300–Door Man【推断无向图欧拉通路】

大家好,又见面了,我是全栈君。

链接:http://poj.org/problem?id=1300

题意:有n个房间。每一个房间有若干个门和别的房间相连。管家从m房间開始走。要回到自己的住处(0),问是否有一条路能够走遍全部的门而且没有反复的路。

无向图欧拉通路充要条件:G为连通图,而且G仅有两个奇度结点(度数为奇数的顶点)或者无奇度结点。

无向图欧拉回路充要条件:G为无奇度结点的连通图。

思路:推断是否存在欧拉通路。依据欧拉通路、欧拉回路的性质来做。有两种情况:一种是欧拉回路。全部房间的门的个数都是偶数个,而且此时初始房间不是0,此时存在要求的路径。假设初始是0则不行。还有一种是欧拉通路。仅仅有两个房间门是奇数个。剩下都是偶数个。而且这两个房间一个是0。一个是当前起点,而且起点不能是0,此时也存在要求的路径,否则不存在。

输入比較蛋疼

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 500100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int in[30],out[30];
char s[20],s1[200];
int main(){
    int i,j;
    int m,n;
    int a,flag,ans,fk;
    while(scanf("%s",s)!=EOF){
        if(s[0]=='E'&&strlen(s)>5)  break;
        scanf("%d%d",&m,&n);
        getchar();
        ans = 0;
        flag = 0;
        fk = 0;
        memset(in,0,sizeof(in));
        for(i=0;i<n+1;i++){
            gets(s1);
            int p = 0;
            while(sscanf(s1+p,"%d",&a)==1){
                ans++;
                in[a]++;
                in[i]++;
                while(s1[p]!='\0'&&s1[p]!=' ')  p++;
                while(s1[p]!='\0'&&s1[p]==' ')  p++;
            }
        }
        for(i=0;i<n;i++){
            if(in[i]&1) flag++;
        }
        if(!flag){
            if(!m)  fk = 1;
            else    fk = 0;
        }
        else{
            if(flag==2&&m!=0&&in[m]&1&&in[0]&1)   fk = 1;
            else    fk = 0;
        }
        if(fk)  printf("YES %d\n",ans);
        else    puts("NO");
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116070.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • montavuego_Vue.js+Flask+MongoDB

    montavuego_Vue.js+Flask+MongoDBMongoVUE是一个可以操作mongodb的图形化客户端,方面查看等使用; 一、下载MongoVUE(绿色激活成功教程版):http://download.csdn.net/detail/u011694549/5945519二、解压,打开文件夹:           三、启动MongoVUE.exe         四、建立连接,即可访问数据库了

  • pycharm多行代码同时缩进快捷键:Tab键,一次缩进四个字符

    pycharm多行代码同时缩进快捷键:Tab键,一次缩进四个字符pycharm使多行代码同时缩进鼠标选中多行代码后,按下Tab键,一次缩进四个字符

    2022年10月30日
  • zabbix监控redis信息

    zabbix监控redis信息了解Redis的info要获得Redis的当前情况,使用info命令即可。具体用法:redis-cli-h127.0.0.1-p6379-aredis_passwdinfo[参数]。针对不同的参数就会看到具体的数字,如果没有带参数,那么就会把默认情况写出来,如果带上all参数,那么就会把所有情况都写出来。比如:redis-cli-h127.0.0.1-p6379-aredis_passwdinfoserver,就会看到redis关于server的一些数据,如下:可以看

  • disk quota exceeded

    磁盘满了之前提过用命令行查看还有一种可视化方法终端输入baobab

  • 多重共性和VIF检验「建议收藏」

    多重共性和VIF检验「建议收藏」图片来源https://wenku.baidu.com/view/7008df8383d049649b66581a.html 和https://wenku.baidu.com/view/6acdf95e52ea551811a68721.html

  • CListCtrl自绘「建议收藏」

    CListCtrl自绘「建议收藏」CListCtrl自绘有3种方法:第一种:使用WM_ERASEBKGND消息+NM_CUSTOMDRAW消息配合自绘WM_ERASEBKGND消息中绘制背景色,比如偶数行为灰色,奇数行为白色。NM_CUSTOMDRAW消息中设置字体的背景色和字体颜色。好处:保留了控件大多数的原有属性。不需要自己去输出每一个项目的字体。可以非常方便的设置背景色,以及文字的颜色。缺点:不能设置选中

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号