POJ--1300--Door Man【推断无向图欧拉通路】
2024-10-19 06:54:29
链接: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;
}
最新文章
- bzoj3157国王奇遇记(秦九韶算法+矩乘)&;&;bzoj233AC达成
- 图形化查看maven的dependency依赖
- The file couldn&#39;t be opened because you don&#39;t have permission to view it
- [New Portal]Windows Azure Virtual Machine (21) 将本地Hyper-V的VM上传至Windows Azure Virtual Machine
- BZOJ1915: [Usaco2010 Open]奶牛的跳格子游戏
- mvc area区域和异步表单,bootstrap简单实例
- Summary: Process &; Tread
- netty概念
- sql server查询出的结果中添加一列序列行
- 摘自淘宝的js地区组件
- 测试框架mochajs详解
- ElasticSearch基本用法
- 初探java对象比较
- VMWare 学习目录
- iOS集合视图单元格高亮和选中的区别
- 超实用的JavaScript代码段 Item1 --倒计时效果
- 【BZOJ 5222】[Lydsy2017省队十连测]怪题
- flask 安装及基础学习(url_for反转,静态文件引入)
- C#:时间日期操作(持续更新)
- RHEL7.3安装python3.6.1
热门文章
- Android数据的四种存储方式SharedPreferences、SQLite、Content Provider和File (四) —— ContentProvider
- (转)经典线程同步 互斥量Mutex
- Maven Spring JUnit 在Maven Clean Install时报
- Android 开发笔记“程序安装包APK的制作”
- (Problem 70)Totient permutation
- MySQL对于有大量重复数据表的处理方法
- C++模板:二分图匹配
- poj 1386 Play on Words(有向图欧拉路+并查集)
- poj 3356 AGTC(线性dp)
- Oracle 经典SQL 专为笔试准备