青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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次,超時(shí)4次,wa 3次。
很無語。
應(yīng)該是動(dòng)態(tài)規(guī)劃最好,但是我不是很熟,用了搜索。以下是超時(shí)的代碼
#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)//返回從當(dāng)前點(diǎn)出發(fā)的最大長(zhǎng)度
{
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;//這句堅(jiān)決不需要 
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)//返回從當(dāng)前點(diǎn)出發(fā)的最大長(zhǎng)度
{
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】。
沒有影響。
假設(shè)改為
5 3 5 2 3 5 3 1 2 4 4 1 0 0 執(zhí)行時(shí)會(huì)走3->1>這時(shí)的1結(jié)點(diǎn)len[1]已經(jīng)求的 3>5>2>4>1len[1]已知了
posted on 2009-06-29 16:13 luis 閱讀(279) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發(fā)題
<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

文章分類

文章檔案

友情鏈接

搜索

  •  

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲福利一区| 亚洲人www| 日韩午夜免费| 亚洲大片av| 蜜桃av久久久亚洲精品| 亚洲国产日韩欧美一区二区三区| 久久躁日日躁aaaaxxxx| 看片网站欧美日韩| 亚洲欧洲精品一区二区| 亚洲全黄一级网站| 欧美四级在线观看| 欧美在线免费视频| 久久噜噜亚洲综合| 一本久久综合| 亚洲女同精品视频| 亚洲国产日韩一区| 欧美日韩精品一区二区| 午夜在线视频观看日韩17c| 欧美在线观看视频一区二区| 亚洲第一精品影视| 亚洲在线第一页| 久久国产色av| 国产精品毛片a∨一区二区三区| 亚洲男人av电影| 久久精品一区二区三区四区| 亚洲美女一区| 欧美亚洲一区三区| 日韩视频在线免费观看| 亚洲欧美视频一区| 99国产精品久久久| 欧美自拍偷拍| 亚洲一区二区三区在线播放| 久久精品99无色码中文字幕| 99精品视频免费全部在线| 午夜精品影院| 亚洲性色视频| 美女精品在线观看| 久久精品国产清高在天天线| 欧美大学生性色视频| 久久精品国产99精品国产亚洲性色| 麻豆精品在线观看| 久久精品中文| 国产精品高潮久久| 亚洲国产精品www| 国产一区二区日韩精品欧美精品 | 欧美日韩在线影院| 久久一区视频| 国产精品一二一区| 亚洲精品在线一区二区| 亚洲黄色毛片| 久久免费精品视频| 久久免费的精品国产v∧| 免费国产一区二区| 久久综合网色—综合色88| 国产精品日韩电影| av成人手机在线| 日韩小视频在线观看专区| 久久天堂成人| 老牛嫩草一区二区三区日本| 国产区精品在线观看| 亚洲无限av看| 亚洲欧美日韩区| 欧美日韩亚洲系列| 日韩一级在线观看| 亚洲少妇自拍| 欧美午夜激情视频| 亚洲一二三四久久| 午夜免费久久久久| 国产精品一区二区久久久| 亚洲一区二区欧美日韩| 香蕉精品999视频一区二区| 国产精品网站在线观看| 亚洲一区久久| 久久精品一区二区三区不卡牛牛| 国产日韩欧美在线播放| 欧美一区观看| 欧美高清视频一区| 亚洲久久成人| 欧美日韩一区二区欧美激情| 中文一区在线| 欧美在线三级| 亚洲第一中文字幕| 欧美人体xx| 亚洲综合导航| 久久人人精品| 亚洲久色影视| 国产精品一区二区在线| 亚洲精品欧美日韩专区| 欧美二区在线观看| 99天天综合性| 国产精品亚洲成人| 久久天天躁夜夜躁狠狠躁2022 | 99国产精品久久| 国产精品色在线| 久久久久成人精品免费播放动漫| 亚洲成色777777在线观看影院| 欧美激情一区二区三区全黄| 一本色道久久综合一区 | 亚洲成人在线网| 欧美色另类天堂2015| 午夜天堂精品久久久久| 亚洲国产精品视频| 欧美一区二区国产| 91久久精品日日躁夜夜躁欧美| 欧美日韩在线另类| 久久久精品视频成人| 亚洲精品美女91| 久久一区二区三区国产精品| 一区二区欧美精品| 黄色精品一区二区| 欧美亚日韩国产aⅴ精品中极品| 欧美在线视频免费| 这里是久久伊人| 亚洲第一区在线| 欧美在线黄色| 一区二区三区视频在线播放| 激情五月综合色婷婷一区二区| 欧美日韩国产免费观看| 久久免费一区| 欧美一区二区成人6969| 在线亚洲观看| 欧美极品一区| 久久久久欧美精品| 亚洲永久精品大片| 99精品99久久久久久宅男| 国产一区视频网站| 国产精品人人做人人爽人人添 | 亚洲国产精品va在线看黑人| 久久精品视频在线看| 午夜激情综合网| 亚洲一品av免费观看| 亚洲精品韩国| 亚洲黄色成人网| 亚洲国产精品欧美一二99| 好看不卡的中文字幕| 国产欧美在线观看一区| 国产精品日韩欧美大师| 国产精品v欧美精品v日本精品动漫| 免费在线亚洲| 欧美成人一区在线| 免费亚洲网站| 欧美成人免费va影院高清| 老司机免费视频一区二区三区| 久久99在线观看| 欧美资源在线| 久热国产精品视频| 免费观看一级特黄欧美大片| 狂野欧美激情性xxxx| 久久夜色精品一区| 久久综合色播五月| 免费在线观看精品| 欧美精品一区在线| 欧美日韩国产免费| 国产精品日韩精品欧美精品| 国产精品视频xxx| 国产亚洲一区二区在线观看| 国产中文一区二区三区| 国外成人在线视频网站| 在线观看成人一级片| 亚洲国产一区二区三区在线播| 亚洲精品五月天| 久久午夜av| 欧美一区二区三区视频| 久久精品国产一区二区三| 久久综合99re88久久爱| 欧美激情视频一区二区三区在线播放 | 亚洲欧美网站| 久久久久久久久久久久久9999| 久久亚洲精选| 亚洲国产色一区| 中文一区在线| 久久天天躁狠狠躁夜夜爽蜜月 | 亚洲欧美国产日韩天堂区| 久久国产精品99国产| 欧美成人日韩| 国产欧美成人| 亚洲欧洲日产国码二区| 亚洲在线免费视频| 久久亚洲精品伦理| 亚洲欧洲在线看| 午夜精品999| 欧美二区在线观看| 国产欧美精品xxxx另类| 最新中文字幕一区二区三区| 欧美一区二区三区的| 亚洲国产精品999| 午夜精品一区二区三区四区| 欧美激情在线播放| 国产一区免费视频| 制服丝袜亚洲播放| 蜜臀va亚洲va欧美va天堂| 一本大道av伊人久久综合| 久久久久久久综合色一本| 国产精品乱子乱xxxx| 久久成人综合网| 久久精品91久久香蕉加勒比| 亚洲精品乱码久久久久久日本蜜臀| 亚洲欧美日韩精品一区二区| 欧美久久视频| 亚洲高清视频在线|