贪心策略、深度优先搜索
网络流模型理论上可以解决此题，把除1和n以外的每个结点都拆成两个结点，中间用一条容量为1的边连接，结点1为源，结点n为汇求最大流。无奈本题数据规模较大，最多有5000个结点，而且边数未知。
注意到题目给出的图具有特殊的性质：边是按从东到西的顺序给出的，而且所有边不相交。这样我们可以采取如下贪心策略：用深度优先搜索从结点1出发找一条尽可能靠东（或尽可能靠西）的路径，让一个运动员沿此路径滑雪，把此路径上的除起点和终点外的所有结点从图中删去，然后重复此过程。这个策略显然正确，由于所有边都不相交，每次找最靠东（或最靠西）的路径可以给后面要找的路径腾出最大的空间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> using namespace std; struct edge { int v; edge *next; edge(int v,edge *next):v(v),next(next) {} } *e[5005]; int n; bool u[5005]; bool dfs(int v) { if(v==n) return true; u[v]=true; for(edge *t=e[v];t;t=t->next) if(!u[t->v]&&dfs(t->v)) return true; return false; } int main() { freopen("nar.in","r",stdin); freopen("nar.out","w",stdout); scanf("%d",&n); int t,v,ans=0; for(int i=1;i<n;++i) for(scanf("%d",&t);t;--t) { scanf("%d",&v); e[i]=new edge(v,e[i]); } for(edge *p=e[1];p;p=p->next) if(!u[p->v]&&dfs(p->v)) ++ans; printf("%d\n",ans); return 0; } |