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]!='
#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; }
'&&s1[p]!=' ') p++; while(s1[p]!='
#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; }
'&&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)


相关推荐

  • git 清除所有untracked file

    git 清除所有untracked file

  • php new reflectionclass,PHP: ReflectionClass – Manual

    php new reflectionclass,PHP: ReflectionClass – ManualReflectionClass::__construct—СоздаётобъектклассаReflectionClassReflectionClass::getConstant—ВозвращаетопределённуюконстантуReflectionClass::getConstructor—ВозвращаетконструкторклассаRefle…

    2022年10月23日
  • css实现横向滚动条(css纵向滚动条)

    注意:(滚动条设置的width、height,分别是对应纵向滚动条宽度、横向滚动条高度,无法修改纵向滚动条高度、横向滚动条宽度数值只介绍Google浏览器滚动条样式,常用属性如下)::-webkit-scrollbar 滚动条整体样式 ::-webkit-scrollbar-button 一设置滚动条样式,滚动条两端的按钮图标就消失,但可以重新设置图片、新样式 ::-w…

  • 憨批的语义分割重制版5——Keras 搭建自己的Unet语义分割平台

    憨批的语义分割重制版5——Keras 搭建自己的Unet语义分割平台憨批的语义分割12——Keras搭建自己的Unet语义分割平台注意事项学习前言什么是Unet模型代码下载Unet实现思路一、预测部分1、主干网络介绍2、加强特征提取结构3、利用特征获得预测结果二、训练部分1、训练文件详解2、LOSS解析训练自己的Unet模型注意事项这是重新构建了的Unet语义分割网络,主要是文件框架上的构建,还有代码的实现,和之前的语义分割网络相比,更加完整也更清晰一些。建议还是学习这个版本的Unet。学习前言重置一下我最喜欢的Unet。什么是Unet模型Unet是一个优秀

  • LRC格式转换

    LRC格式转换[code="java"]importjava.io.BufferedReader;importjava.io.FileInputStream;importjava.io.FileNotFoundException;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.Co…

    2022年10月22日
  • 浅谈 Java 中的 Class 类

    浅谈 Java 中的 Class 类万事万物皆对象,类也是对象,是java.lang.class类的对象。理解了Class类,我么才能更好的理解Java的反射机制。

发表回复

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

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