Codeforces 350B Resort

题目链接：http://codeforces.com/problemset/problem/350/B

一开始想复杂了，建了张图，结果效率太低T了。其实用数组存可以了，结果发现的时候快没时间了，修改好前5分钟比赛就结束了，泪目。。。

题目大意：每个地点有用1表示旅馆，用0表示是山地。每个地点用一个数表示能从哪一个地点到达这里(单向)。现在要求一条最长的路径，除了终点为旅馆外，前面的路径上都是山地。要求前面的路上不能有分岔路，即从该点出发只有一条可行路。

解题思路：开一个数组存到达该点的始发地，再开一个数组存以某点为起点的路径有几条，不为1即可删去不计。然后从每一个旅馆开始向前深搜，找出最长的路径。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define N 100005

 #define M 200010

 int ob[N],ro[N];

 int hotel[N],K,road[N],road2[N];//hotel记录每个旅馆的位置，road存最长路径

 int v[N],link[N];//v记录到达该点的始发地，link记录以每一个点为起点有多少条路径

 void dfs(int now ,int num)//now表示搜到了哪一个，num表示加上该点路径有多长

 {

     int i,k;

     if(link[now]>)

     {

         return;

     }

     road2[num-]=now;

     if(K<num&&(link[v[now]]>||v[now]==))//当搜到下一个点有超过一条路径，或者连接该点的是一条无效路径时可更新最大值

     {

         K=num;

         for(i=;i<K;i++)

             road[i]=road2[i];

     }

     if(v[now]&&link[v[now]]<=)

         dfs(v[now],num+);

 }

 int main()

 {

     memset(link,,sizeof(link));

     int n,i,cnt=,e=;

     scanf("%d",&n);

     for(i=;i<=n;i++)

     {

         scanf("%d",&ob[i]);

         if(ob[i]==)

             hotel[cnt++]=i;

     }

     for(i=;i<=n;i++)

     {

         scanf("%d",&ro[i]);

         if(ro[i]){

             v[i]=ro[i];

             link[ro[i]]+=;

         }

     }

     for(i=;i<cnt;i++)

     {

         if(K==)

         {

             K=;

             road[]=hotel[i];

         }

         dfs(hotel[i],);

     }

     printf("%d\n",K);

     for(i=K-;i>=;i--)

     {

         if(i)

             printf("%d ",road[i]);

         else

             printf("%d",road[i]);

     }

     printf("\n");

     return ;

 }

巴特西

Codeforces 350B Resort

最新文章

热门文章