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

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>
            国产精品一区在线播放| 亚洲精品乱码久久久久久日本蜜臀| 欧美va亚洲va香蕉在线| 欧美在线关看| 激情综合亚洲| 欧美激情在线狂野欧美精品| 欧美/亚洲一区| 一区二区三区精品视频| 在线视频精品一区| 国产婷婷色一区二区三区在线 | 一二三四社区欧美黄| 亚洲精品视频一区| 国产精品视频一区二区高潮| 久久久国产精品一区二区中文| 久久久91精品| 99精品国产在热久久婷婷| 在线视频日韩| 国内一区二区三区在线视频| 欧美激情精品久久久久久变态| 欧美绝品在线观看成人午夜影视| 午夜宅男久久久| 免费久久99精品国产自| 亚洲在线一区| 久久久噜噜噜| 性18欧美另类| 免费黄网站欧美| 性伦欧美刺激片在线观看| 久久精品国产亚洲一区二区| 亚洲精品视频在线看| 欧美精品久久久久久久久久| 一本色道久久综合亚洲二区三区| 日韩亚洲欧美一区| 国产日本欧美一区二区三区在线 | 99亚洲精品| 亚洲男人的天堂在线| 亚洲日本视频| 欧美怡红院视频| 一区二区三区成人| 久久综合色8888| 欧美亚洲尤物久久| 欧美日韩激情小视频| 免费成人网www| 国产日韩一区欧美| 在线亚洲高清视频| 日韩小视频在线观看专区| 欧美怡红院视频一区二区三区| 一本色道**综合亚洲精品蜜桃冫| 久久久国产一区二区| 亚洲在线一区二区| 欧美日韩视频| 亚洲精选91| 亚洲精品资源| 久久香蕉国产线看观看网| 久久精品视频播放| 国产精品久久久久秋霞鲁丝| 亚洲国产精品www| 狠狠色丁香久久综合频道| 妖精视频成人观看www| 精品成人一区二区| 亚洲欧美日韩视频二区| 亚洲图片自拍偷拍| 久久视频在线看| 久久九九精品| 韩国精品一区二区三区| 欧美在线一二三区| 久久久久久久综合| 国产视频久久网| 欧美一级电影久久| 久久久久.com| 国产亚洲激情在线| 欧美呦呦网站| 狠狠色狠狠色综合日日小说| 亚洲主播在线| 欧美成人精品一区二区| 免费在线看成人av| 亚洲第一搞黄网站| 麻豆成人91精品二区三区| 欧美激情视频网站| 日韩视频免费在线| 牛牛精品成人免费视频| 亚洲欧洲在线免费| 日韩视频一区| 国产精品视频网址| 久久久亚洲国产美女国产盗摄| 嫩草成人www欧美| 亚洲清纯自拍| 国产精品久久久久久福利一牛影视| 一区二区电影免费观看| 欧美综合第一页| 永久555www成人免费| 欧美aa在线视频| 亚洲免费一在线| 午夜欧美大尺度福利影院在线看| 国产一区视频网站| 欧美成人一区二区| 亚洲欧美日韩一区在线| 欧美成人一品| 午夜精品福利一区二区蜜股av| 国产精品国产三级国产专区53| 欧美一区二区三区视频在线| 亚洲欧洲视频| 久久久蜜桃精品| 亚洲区免费影片| 国产精品综合av一区二区国产馆| 久久久夜精品| 亚洲一区二区三区在线播放| 老司机久久99久久精品播放免费 | 狠狠色综合日日| 欧美日韩另类综合| 久久都是精品| 亚洲一线二线三线久久久| 美日韩丰满少妇在线观看| 亚洲一品av免费观看| 永久免费毛片在线播放不卡| 国产精品高潮呻吟视频| 欧美成人国产| 性欧美1819sex性高清| 亚洲乱码国产乱码精品精可以看| 久久蜜桃资源一区二区老牛| 亚洲欧美文学| 一本色道久久88综合亚洲精品ⅰ | 国产香蕉久久精品综合网| 欧美精品一区二区三区蜜桃| 久久另类ts人妖一区二区| 亚洲专区在线视频| 一本久道久久综合狠狠爱| 欧美福利视频| 麻豆乱码国产一区二区三区| 校园春色国产精品| 亚洲午夜精品网| 日韩午夜激情| 亚洲美女中出| 亚洲人精品午夜| 91久久精品www人人做人人爽| 好吊日精品视频| 国产一区久久久| 国产区二精品视| 国产日韩欧美在线视频观看| 国产精品久久999| 国产精品久久久久高潮| 国产精品99一区二区| 欧美三级韩国三级日本三斤| 欧美经典一区二区| 欧美精品www| 欧美日韩亚洲三区| 欧美日韩视频在线| 欧美亚州一区二区三区| 国产精品乱码人人做人人爱| 国产精品国码视频| 国产精品亚洲а∨天堂免在线| 国产精品欧美日韩一区二区| 国产精品亚发布| 一区精品久久| 亚洲国产日韩欧美综合久久 | 激情综合五月天| 亚洲欧洲精品天堂一级| 亚洲美女区一区| 亚洲一区二区三区色| 欧美一区二区三区视频| 欧美在线不卡| 免费的成人av| 亚洲精品久久久久| 亚洲午夜精品17c| 欧美一区91| 久久亚洲综合色| 欧美大色视频| 国产精品免费aⅴ片在线观看| 国产精品丝袜xxxxxxx| 韩国成人福利片在线播放| 亚洲欧洲一区二区三区| 亚洲欧洲99久久| 久久综合九色九九| 日韩视频一区二区在线观看 | 国产精品综合久久久| 永久555www成人免费| 亚洲午夜一二三区视频| 久久成人精品| 亚洲人成人一区二区在线观看| 亚洲一区www| 美女黄色成人网| 国产九九精品| 亚洲精品一区二区三| 欧美一区影院| 欧美国产日韩精品| 亚洲免费视频成人| 欧美a级片网站| 国产日本欧美一区二区三区在线 | 最新国产精品拍自在线播放| 欧美一区亚洲| 日韩一区二区久久| 久久综合色8888| 国产日韩欧美不卡| 亚洲先锋成人| 亚洲激情校园春色| 久久国产视频网站| 国产精品美女久久久久av超清 | 欧美亚一区二区| 日韩视频精品在线| 欧美成人午夜激情视频| 欧美一区在线视频|