POJ 1300 - 阅读理解+恶心输入+欧拉回路
题意不太好理解....大致上: 是从某个指定的房间出发...问能否回到0房间...并且关掉图中所有的门..而门是关上后无法打开的...
输入比较奇葩..我是gets读入一行后再处理的...
再抽象一些...把门开作边..那么相当于找一条路径..使得便利所有的边..且每个边只遍历一次...这里分为两种情况..一种是从0出发..走完所有的边回到0...这是典型的欧拉回路...另一种是从其他点出发..到达0点..并且走完所有的边..
判断一个图能否存在欧拉回路..就是看所有点的度是否为偶数...因为所有的点必定都是进入多少次就要出去多少次...而只是一条路路径而非回路..那么起点和终点必须是奇数的度..而其他的点的度必须为偶数...
Program：
#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#include<map>#include<queue>#include<stack>#define ll long long#define oo 1000000000#define pi acos(-1)using namespace std; int m,n,ans,a[105];char s[505];int main(){ int p,len,i,k; while (~scanf("%s",s)) { if (s[0]!='S') break; scanf("%d%d",&m,&n); gets(s); memset(a,0,sizeof(a)); ans=0; for (p=0;p<n;p++) { gets(s); len=strlen(s); i=0; while (i<len) { k=0; while (s[i]>='0' && s[i]<='9') { k=k*10+s[i]-'0'; i++; } if (k) { a[p]++; a[k]++; ans++; k=0; } i++; } } gets(s); k=0; for (i=0;i<n;i++) if (a[i]%2) k++; if (!m) { if (!k) printf("YES %d\n",ans); else printf("NO\n"); }else { if (k==2 && a[m]%2 && a[0]%2) printf("YES %d\n",ans); else printf("NO\n"); } } return 0;}