POJ--1300--Door Man【推断无向图欧拉通路】-白红宇

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

阅读量：5134 次

发布时间：2019-06-13

本文共 1150 字，大约阅读时间需要 3 分钟。

链接：

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

无向图欧拉通路充要条件：G为连通图，而且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。

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

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

输入比較蛋疼

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      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|1int 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

转载于:https://www.cnblogs.com/yxwkf/p/5178597.html

你可能感兴趣的文章