大家好,又见面了,我是全栈君。
链接: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账号...