USACO Street Race

第一问很简单，只需要尝试把各点从图上去除，然后从出发点开始遍历，如果不能到达终点，那么这个点就是“不可避免”的。

第二问困扰了我很长一段时间。题目中是这么说的：

A point S is a splitting point for the well-formed course C if S differs from the start and the finish of C, and the course can be split into two well-formed courses that (1) have no common arrows and (2) have S as their only common point, with S appearing as the finish of one and the start of the other.

最后迫不得已看了NOCOW上的题解，其实上面这些话的意思就是第一天可以到达的点和第二天可以到达的点不能重复。因此，只需要两次遍历就足够了。并且满足第二问限制的点一定满足第一问限制。

不过，为什么是这样的我还没有折腾明白，各位读者如有思路麻烦留言下，谢了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MXN 55
005 #define S 0
006 #define F (N-1)
007
008 int adj[MXN][MXN] = {};
009 int N;
010
011 void init()
012 {
013     int tmp;
014     while(1)
015     {
016         while(1)
017         {
018             scanf("%d",&tmp);
019             if(tmp == -2)
020                 break;
021             else if(tmp == -1)
022                 return;
023             else if(N != tmp)  //ignore self loop
024             {
025                 adj[N][tmp] = 1;
026             }
027         }
028         N ++;
029     }
030 }
031
032 int queue[MXN * 10];
033 int head,tail;
034
035 void enqueue(int node)
036 {
037     queue[tail ++] = node;
038 }
039
040 int dequeue()
041 {
042     return queue[head ++];
043 }
044
045 int check_connectivity(int exclude)    //BFS from start
046 {
047     int now,i;
048     int visit[MXN];
049     head = tail = 0;
050     memset(visit,0,sizeof(visit));
051     enqueue(S);
052     visit[S] = 1;
053     while(head < tail)
054     {
055         now = dequeue();
056         for(i = 0;i < N;i ++)
057             if(adj[now][i] && i != exclude && !visit[i])
058             {
059                 enqueue(i);
060                 visit[i] = 1;
061             }
062     }
063     if(visit[F])    return 1;
064     return 0;
065 }
066
067 int have_common_node(int mid)
068 {
069     static _Bool visit[MXN];
070     static int first[MXN],second[MXN];
071     int i,now;
072    
073     head = tail = 0;
074     memset(visit,0,sizeof(visit));
075     memset(first,0,sizeof(first));
076     memset(second,0,sizeof(second));
077     enqueue(S);
078     first[S] = visit[S] = 1;
079     while(head < tail)
080     {
081         now = dequeue();
082         for(i = 0;i < N;i ++)
083         {
084             if(adj[now][i] && !visit[i] && i != mid)
085             {
086                 enqueue(i);
087                 visit[i] = 1;
088                 first[i] = 1;
089             }
090         }
091     }
092    
093     memset(visit,0,sizeof(visit));
094     head = tail = 0;
095     enqueue(mid);
096     second[mid] = visit[mid] = 1;
097     while(head < tail)
098     {
099         now = dequeue();
100         for(i = 0;i < N;i ++)
101         {
102             if(adj[now][i] && !visit[i])
103             {
104                 enqueue(i);
105                 visit[i] = 1;
106                 second[i] = 1;
107             }
108         }
109     }
110     fprintf(stderr,"\n%d:\n",mid);
111     for(i = 0;i < N;i ++)
112     {
113         fprintf(stderr,"%d: %d %d\n",i,first[i],second[i]);
114     }
115    
116     for(i = 0;i < N;i ++)
117     {
118         if(i == mid)    continue;
119         if(first[i] && second[i])    return 1;
120     }
121     return 0;
122 }
123
124 int main()
125 {
126     freopen("race3.in","r",stdin);
127     freopen("race3.out","w",stdout);
128     int i;
129     int ucnt = 0,scnt = 0;
130     int unavoid[MXN] = {};
131     int split[MXN] = {};
132     init();
133     //try unavoidable nodes
134     for(i = 0;i < N;i ++)
135     {
136         if(i == S || i == F)    continue;
137         if(check_connectivity(i) == 0)
138         {
139             unavoid[ucnt ++] = i;
140             if(have_common_node(i) == 0)
141                 split[scnt ++] = i;
142         }
143     }
144     printf("%d",ucnt);
145     for(i = 0;i < ucnt;i ++)
146         printf(" %d",unavoid[i]);
147     printf("\n");
148     printf("%d",scnt);
149     for(i = 0;i < scnt;i ++)
150         printf(" %d",split[i]);
151     printf("\n");
152    
153     return 0;
154 }