USACO Section 4.3 Street Race - 简单搜索

50个点...100条边....数据量很小...第一问就直接枚举去掉每个点看能否到达终点~~~N次BFS就ok了...

第二问~~首先第二问的点肯定是第一问的点的子集~~这个应该好想到..然后就按他的描述...枚举第一问得到的点..从起点开始BFS到枚举的这个点记录能到达的点..从枚举的这个点开始BFS到终点并记录所能到达的点...若两者标记的点中没有重复则说明这个第一问的点同时满足第二问的要求~

Program:

/* ID: zzyzzy12 LANG: C++ TASK: race3 */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node { int x,y,next; }line[305]; int n,m,_link[55],Ans1[55],Ans1Num; bool used[55]; queue<int> myqueue; void getanswer1() { int p=1,h,k; Ans1Num=0; for (p=1;p<n;p++) { while (!myqueue.empty()) myqueue.pop(); memset(used,false,sizeof(used)); used[p]=true; used[0]=true; myqueue.push(0); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); k=_link[h]; while (k) { if (!used[line[k].y]) { used[line[k].y]=true; myqueue.push(line[k].y); } k=line[k].next; } } if (!used[n]) Ans1[++Ans1Num]=p; } printf("%d",Ans1Num); for (p=1;p<=Ans1Num;p++) printf(" %d",Ans1[p]); printf("\n"); return; } void getanswer2() { int Ans2Num,Ans2[55],p,h,k; bool f[55]; Ans2Num=0; for (p=1;p<=Ans1Num;p++) { while (!myqueue.empty()) myqueue.pop(); memset(f,false,sizeof(f)); f[Ans1[p]]=true; myqueue.push(Ans1[p]); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); k=_link[h]; while (k) { if (!f[line[k].y]) { f[line[k].y]=true; myqueue.push(line[k].y); } k=line[k].next; } } memset(used,false,sizeof(used)); used[0]=true; myqueue.push(0); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); if (h==Ans1[p]) continue; if (f[h]) goto A; k=_link[h]; while (k) { if (!used[line[k].y]) { used[line[k].y]=true; myqueue.push(line[k].y); } k=line[k].next; } } Ans2[++Ans2Num]=Ans1[p]; A: ; } printf("%d",Ans2Num); for (k=1;k<=Ans2Num;k++) printf(" %d",Ans2[k]); printf("\n"); return; } int main() { freopen("race3.in","r",stdin); freopen("race3.out","w",stdout); int i,y; m=0; n=-1; memset(_link,0,sizeof(_link)); while (1) { scanf("%d",&y); if (y==-1) break; n++; while (y!=-2) { m++; line[m].x=n; line[m].y=y; line[m].next=_link[n]; _link[n]=m; scanf("%d",&y); } } getanswer1(); getanswer2(); return 0; }