• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0
            I have my friends to visit. For some reason, I can only visit some of my friends. So I want see my friends as many as possible. Thus I must choose the longest way. Your goal is to help me developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (My residence). You can assume that the graph has no cycles (there is no path from any node to itself), so I will reach my destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves.

            Input

            The input consists of a number of cases. The first line on each case contains a positive number n (1 < n <= 100) that specifies the number of points in the graph. A value of n = 0 indicates the end of the input. After this, a second number s is provided, indicating the starting point in my journey (1 <= s <= n). Then, you are given a list of pairs of places p and q, one pair per line. The pair "p q" indicates that I can visit q after p. A pair of zeros ("0 0") indicates the end of the case. As mentioned before, you can assume that the graphs provided will not be cyclic.

            Output

            For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.

            Print a new line after each test case.

            Sample Input

            2
            1
            1 2
            0 0
            5
            3
            1 2
            3 5
            3 1
            2 4
            4 5
            0 0
            5
            5
            5 1
            5 2
            5 3
            5 4
            4 1
            4 2
            0 0
            0
            

            Sample Output

            Case 1: The longest path from 1 has length 1, finishing at 2.
            Case 2: The longest path from 3 has length 4, finishing at 5.
            Case 3: The longest path from 5 has length 2, finishing at 1.
            提交了10次,AC 3次,超時4次,wa 3次。
            很無語。
            應該是動態(tài)規(guī)劃最好,但是我不是很熟,用了搜索。以下是超時的代碼
            #include<iostream>
            #include<cstdlib>
            using namespace std;
            int path[101][101];
            int mark[101];
            int len[101];//
            int end[101];
            int dfs(int start,int num)//返回從當前點出發(fā)的最大長度
            {
            if(mark[start]==1)return len[start];
            mark[start]=1;
            end[start]=start;
            for(int i=1;i<=num;i++)
            {
            if(path[start][i])
            {
            if(len[start]<dfs(i,num)+1)
            {
            len[start]=len[i]+1;
            end[start]=end[i];
            }
            else
            if(len[start]==len[i]+1&&end[start]>end[i])
            end[start]=end[i];
            }
            }
            mark[start]=0;//這句堅決不需要 
            return len[start];
            }
            int main()
            {
            // freopen("s.txt","r",stdin);
            //freopen("key.txt","w",stdout);
            int j,k,turn=0;
            int start,num;
            while(cin>>num)
            {
            turn++;
            if(num==0)break;
            memset(path,0,sizeof(path));
            memset(mark,0,sizeof(mark));
            memset(len,0,sizeof(len));
            memset(end,0,sizeof(end));
            cin>>start;
            while(cin>>j>>k)
            {
            if(j==0)break;
            path[j][k]=1;
            }
            cout<<"Case "<<turn<<": The longest path from "<<start<<" has length "<<dfs(start,num)<<", finishing at "<<end[start]<<"."<<endl<<endl;
            }
            //system("PAUSE");
            return   0;
            }
            以下是ac的代碼
            #include<iostream>
            #include<cstdlib>
            using namespace std;
            int path[102][102];
            int mark[102], len[102],end[102];
            int dfs(int start,int num)//返回從當前點出發(fā)的最大長度
            {
            if(mark[start]==1)return len[start];
            mark[start]=1;
            end[start]=start;
            len[start]=0;
            int i,t;
            for( i=1;i<=num;i++)
            {
            if(path[start][i])
            {
            t=dfs(i,num)+1;
            if(t>len[start])
            {
            len[start]=t;
            end[start]=end[i];
            }
            else
            if(len[start]==t)
            {
            if(end[start]>end[i])
            end[start]=end[i];
            }
            }
            }
            return len[start];
            }
            int main()
            {
            //freopen("s.txt","r",stdin);
            //freopen("key.txt","w",stdout);
            int j,k,turn=0;
            int start,num;
            while(cin>>num,num)
            {
            turn++;
            memset(path,0,sizeof(path));
            memset(mark,0,sizeof(mark));
            memset(len,0,sizeof(len));
            memset(end,0,sizeof(end));
            cin>>start;
            while(cin>>j>>k,j||k)
            {
            path[j][k]=1;
            }
            dfs(start,num);
            cout<<"Case "<<turn<<": The longest path from "<<start<<" has length "<<len[start]<<", finishing at "<<end[start]<<"."<<endl<<endl;
            }
            //system("PAUSE");
            return   0;
            }
            不妨執(zhí)行一下
            5
            3
            1 2
            3 5
            3 1
            2 4
            4 5
            0 0
            先是len[3]=0;end[3]=3;flag[3]=1;
            再執(zhí)行t=dfs(1)+1,
            轉(zhuǎn)入dfs(1);len[1]=0;end[1]=1;flag[1]=1;
            再執(zhí)行t=dfs(2)+1;
            轉(zhuǎn)入dfs(2),len[2]=0;end[2]=2;flag[2]=1;
            再執(zhí)行t=dfs(4)+1
            轉(zhuǎn)入dfs(4),len[4]=0;end[4]=4;flag[4]=1;
            再轉(zhuǎn)入t=dfs(5)+1;
            轉(zhuǎn)入dfs(5),len[5]=0;end[5]=5;flag[5]=1;return(len[5]=0);
            則t=1;t>len[4];len[4]=1;end[4]=end[5]=5;再看4沒了其他相鄰元素。dfs(4)=return(len[4])=1;
            t=dfs(4)+1=2;len[2]=t=2;end[2]=end[4]=5;再看2沒了其他相鄰元素,dfs(2)=return(len(2)=2;
            再看t=dfs(2)+1=3;len[1]=t=3;end[1]=en[2]=5;再看1有沒有其他相鄰元素,dfs(1)=return(len(1)=3
            再執(zhí)行t=dfs(1)+1,len[3]=4;end[3]=end[1]=5;再看3有沒有其他相鄰元素,有dfs(5),已經(jīng)遍歷到了,所以dfs(5)return len【5】。
            沒有影響。
            假設改為
            5 3 5 2 3 5 3 1 2 4 4 1 0 0 執(zhí)行時會走3->1>這時的1結(jié)點len[1]已經(jīng)求的 3>5>2>4>1len[1]已知了
            posted on 2009-06-29 16:13 luis 閱讀(273) 評論(0)  編輯 收藏 引用 所屬分類: 搜索 、給我啟發(fā)題
            <2012年11月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品久久久久久影院 | 久久久精品国产| 久久精品国产亚洲AV大全| 久久九九兔免费精品6| 青青久久精品国产免费看| 91麻精品国产91久久久久| 久久国产精品久久国产精品| 久久精品水蜜桃av综合天堂| 无码人妻久久久一区二区三区| 久久人人爽人人爽人人片av麻烦 | 狠狠色综合网站久久久久久久 | 久久精品国产影库免费看| 精品久久久久久久无码| 欧美牲交A欧牲交aⅴ久久| 亚洲午夜久久久影院| 亚洲狠狠婷婷综合久久蜜芽| 久久精品国产免费观看三人同眠| 怡红院日本一道日本久久| 久久精品国产精品青草app| 热久久这里只有精品| 91久久精品国产91性色也| 国内精品伊人久久久久影院对白 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 一本一道久久a久久精品综合| 久久久久久狠狠丁香| 精品久久久久久国产牛牛app| 久久久久国产精品麻豆AR影院| 色婷婷噜噜久久国产精品12p| 亚洲色欲久久久久综合网| 97香蕉久久夜色精品国产| 亚洲中文久久精品无码| 99久久国产综合精品麻豆| 91精品国产91热久久久久福利| 久久精品国产亚洲AV不卡| 亚洲精品第一综合99久久| 久久久久女人精品毛片| 狠狠精品干练久久久无码中文字幕 | 人妻精品久久久久中文字幕| 久久久一本精品99久久精品88| 久久人妻少妇嫩草AV无码专区| 久久久久久狠狠丁香|