描述
Shrek是一个大山里的邮递员,每天负责给所在地区的n个村庄派发信件。但杯具的是,由于道路狭窄,年久失修,村庄间的道路都只能单向通过,甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。
Shrek希望知道如何选定一个村庄A作为起点(我们将他空投到该村庄),依次经过尽可能多的村庄,路途中的每个村庄都经过仅一次,最终到达终点村庄B,完成整个送信过程。这个任务交给你来完成。
输入
第一行包括两个整数n,m,分别表示村庄的个数以及可以通行的道路的数目。
以下共m行,每行用两个整数v1和v2表示一条道路,两个整数分别为道路连接的村庄号,道路的方向为从v1至v2,n个村庄编号为[1, n]。
输出
输出一个数字,表示符合条件的最长道路经过的村庄数。
输入样例
4 3
1 4
2 4
4 3
输出样例
3
限制
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
输入保证道路之间没有形成环
时间:2 sec
空间:256MB
呜~~我受够了~~~
一开始用深度遍历,结果只跑了60分,说我慢了~~然后我就开始憋大招,编了一个晚上,用出度的办法一层层剥掉路径树~~然后想着,先放到OJ上看看对不对再剪枝吧~~~结果,结果清华OJ竟然不让用vector !!!
简直疯掉了~~从网上找了vector.h打包交上,竟然编译不通过!!!难不成让我自己写几千行的代码?~~一想到我竟然还用到了vector的push_back等函数,就觉得绝望,这要是真写那可就是要写好几个内部的接口函数的啊~~疯掉了~~太晚了~~太打击了~~~我去睡觉了~~
对了,有没有大神来看看我的代码对不对的?
#include
#include
using namespace std;
vector
vector
vector
int main()
{
int n,m,v1,v2,i,t;
cin>>n>>m;
for(i=0;i
for(t=0;t
mgraph.push_back(0);
}
outdegree.push_back(0);
length.push_back(0);
}
//cout<
for(i=0;i
cin>>v1>>v2;
mgraph[n*v1+v2]=1;
}
//cout<<"ok2";
for(v1=1;v1 int zero,hight=0; } for(t=0;t //cout<<"hight="< cout< //cout<
t=0;
for(v2=1;v2
if(mgraph[n*v1+v2]==1) t++;
}
outdegree[v1]=t;
}
//cout<
vector
do
{
hight++;
zero=0;
for(v1=1;v1
if(outdegree[v1]==0 && length[v1]==0)
{
zero++;
length[v1]=hight;//cout<<"v1="<
for(i=1;i
if(mgraph[n*i+temp[t]]==1)
{
mgraph[n*i+temp[t]]=0;outdegree[i]–;
//cout<
}
}
temp.clear();
//cout<<"ok5";
}
Pingback引用通告: BZ编程小组 作品 | BZ编程小组